这是多重背包的模版:
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?