背包dp求调
查看原帖
背包dp求调
584977
Susking楼主2022/7/13 16:48

蒟蒻表示不知道怎么回事,只得了最后一个点的十分

经过修改,最后高达十分

看了题解修改后高达十分

疑惑不解,故请大佬指明方向orz

#include<bits/stdc++.h>
using namespace std;
int n,m,w[2333],dp[2333],g[2333]; 
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d",&w[i]);
	dp[0]=1;
	for(int i=1;i<=n;++i){
		for(int j=m;j>=w[j];--j){
			dp[j]=(dp[j]+dp[j-w[i]])%10;
		}
	}
	for(int i=1;i<=n;++i){
		g[0]=1;
//		for(int j=1;j<w[i] &&j<=m;++j){
//			
//			printf("%d",g[j]);
//		}
		for(int j=1;j<=m;++j){
			if(j<w[i]) g[j]=dp[j]%10;
			else g[j]=(dp[j]-g[j-w[i]]+10)%10;
			printf("%d",g[j]);
		}
		printf("\n");
	}
	return 0;
}
2022/7/13 16:48
加载中...