为
https://www.acwing.com/solution/content/21995/
补充一点讲解
把区间从[-m, +m]
压缩到[0,+m]
;
也就是把f[i][j]
和f[i][-j]
都压缩到f[i][j]
由于只要我们能枚举出f[i][j]
则我们一定能枚举出f[i][-j]
,(把砝码左右替换就好了),所以只要f[i][j]
和f[i][-j]
有一个为ture
另一个就也是true
,然后我们就可以把f[i][j]
和f[i][-j]
都压缩到f[i][j]
其中
-
f[i][j] = f[i - 1][j] | f[i - 1][j - w[i]] | f[i - 1][j + w[i]]
(f[i - 1][j - w[i]]
和f[i - 1][j + w[i]
不一定存在) -
f[i][-j] = f[i - 1][-j] | f[i - 1][-j - w[i]] | f[i - 1][-j + w[i]]
(f[i - 1][-j - w[i]]
和f[i - 1][-j + w[i]
不一定存在)
f[i][j] = f[i][j] | f[i][-j]
= f[i - 1][j] | f[i - 1][j - w[i]] | f[i - 1][j + w[i]]
| f[i - 1][-j] | f[i - 1][-j - w[i]] | f[i - 1][-j + w[i]]
/* 全翻到正数
f[i-1][j] | f[i-1][-j] -> f[i-1][j]
f[i-1][j-w[i]] | f[i-1][-j+w[i]] -> f[i-1][abs(j-w[i])]
f[i-1][j+w[i]] | f[i-1][-j-w[i]] -> f[i-1][j+w[i]]
// 其中j, j + w[i]为非负数,但是j - w[i]不一定,所以要套上abs()
*/
= f[i - 1][j] | f[i - 1][j + w[i]] | f[i - 1][abs(j - w[i])];
故原式=f[i - 1][j] | f[i - 1][j + w[i]] | f[i - 1][abs(j - w[i])];
要求从[-m, +m],变为[0, +m],
j, j + w[i], abs(j - w[i])都要满足
代码:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, M = 100010;
bool f[N][M];
int w[N];
int n, m;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++) scanf("%d", &w[i]), m += w[i];
f[0][0] = true;
for (int i = 1; i <= n; i ++)
for (int j = 0; j <= m; j ++)
{
// 应为0 <= j <= m, 所以一定满足-m <= j - w[i] <= +m,所以不用判断
f[i][j] = f[i - 1][j] | f[i - 1][abs(j - w[i])];
if (j + w[i] <= m) f[i][j] |= f[i - 1][j + w[i]];
}
int res = 0;
// 题目要求是计算一共可以称出多少种不同的正整数重量
for (int j = 1; j <= m; j ++) res += f[n][j];
printf("%d\n", res);
return 0;
}