多重背包模版上加个判断就过了?
  • 板块P10973 Coins
  • 楼主GWBailang
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/10/6 21:47
  • 上次更新2024/10/7 08:03:37
查看原帖
多重背包模版上加个判断就过了?
559442
GWBailang楼主2024/10/6 21:47

这是多重背包的模版:


		for(int i=1;i<=n;i++){
			for(int j=m;j>=a[i];j--){
				for(int k=1;k<=c[i]&&k*a[i]<=j;k++){
					dp[j]|=dp[j-k*a[i]];
				}
			}
		}

但是只用在第三层循环外面加个 if(dp[j])continue; 就A了(已经可以凑出的值就不用继续凑了,因此可以跳过)?提交记录,甚至 269 ms。

然后某dalao自己造的hack数据也被这个程序过了:link

话说这个写法的平均复杂度到底是多少,能不能被 hack?

2024/10/6 21:47
加载中...