下午T2求思路

[郭子路]

求思路

现在的定义：
dp[i]表示选i个数时大于等于m的最小数之和;
不会转移

[董子豪 (只会打暴力的人)]

01背包会吗？

[郭子路]

嗯，所以？

[桑沫严]

就是01背包，可以超出的那种

f[0]=true;
for(int i=1;i<=n;i++){
  for(int j=m-1;j>=0;j--){
     f[j+a[i]]=f[j+a[i]]|f[j];
  }
}

[郭子路]

哦…啥也不会的我沉默了

[郭子路]

@桑沫严

[j+a[i]]=f[j+a[i]]|f[j];

还有人吗？这个啥意思“|” ？

[桑沫严]

就是或的意思呀

[桑沫严]

设当前数为 a_i ，若 j 可以到达，那 j+a_i 肯定也能到达

[郭子路]

就这么写？那赋的那个值呀？

[桑沫严]

f 是 bool 类型啊

[桑沫严]

@郭子路 对了，记得特判，如果所有数的总和小于 m 就输出 -1

[郭子路]

嗯嗯，谢谢

[郭子路]

桑，咱俩写法好像不太一样

[郭子路]

for(int i=1;i<=n;++i){
	scanf("%d",&s),cnt+=s;
	for(int j=cnt;j>=s;--j)f[j]=f[j-s]|f[j];
}

[郭子路]

我是这么写的

[桑沫严]

也可以