分组背包大雾
查看原帖
分组背包大雾
499231
Jacky2009楼主2022/6/7 23:46
for(int i=1;i<=cnt;i++){
		for(int j=n;j>=0;j--){
			for(int k=0;k<vl2[i].size();k++){
				if(j<vl2[i][k].siz)continue;
				dp[j]=max(dp[j],dp[j-vl2[i][k].siz]+vl2[i][k].val);
			}
		}
	}

以上就是我用分组背包AC的核心代码。可见这用了滚动数组“优化”(bushi


然而删掉滚动数组变成

for(int i=1;i<=cnt;i++){
   	for(int j=n;j>=0;j--){
   		for(int k=0;k<vl2[i].size();k++){
   			if(j<vl2[i][k].siz)continue;
   			dp[i][j]=max(dp[i][j],dp[i-1][j-vl2[i][k].siz]+vl2[i][k].val);
   		}
   	}
   }

就WA20pts了。 本蒟蒻十分大雾,希望各位神犇能给予援助。

2022/6/7 23:46
加载中...