AcWing 3417. 砝码称重
原题链接
中等
作者:
ofs
,
2024-04-11 23:39:40
,
所有人可见
,
阅读 2
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl "\n"
using namespace std;
const int N = 110, M = 200010, B = M / 2;
/*
能够称出来的总重其实是-10000到10000,全放在某一边
对于f的第二维的取值,从-1e5-5到+1e5+5,数组下标不为负数,所以需要都加上一个偏移量
这样下标从0-200010,f[0][0]变成 f[0][B], f[0][-1e5-5]变成 f[0][0]
*/
int n, m;//砝码的数量 与法码的总重
int w[N];//每个砝码的重量
bool f[N][M];//是否存在一种方案,从前N种法码中取,最后能够称出重量M
//默认说有的状态都是false,如果有需要改变的初值,额外特殊赋值
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for (int i = 1; i <= n; i ++ ) cin>>w[i], m += w[i];//m计算的是现有的砝码的总重
//根据实际意义进行初值的改变
f[0][B]=true;//取0个砝码,称出0,该开始就存在,设置为true
for (int i = 1; i <= n; i ++ )
for (int j = -m; j <= m; j ++ )//注意j的取值
{
f[i][j + B] = f[i - 1][j + B];
//当 j - w[i] >= -m,才会存在 f[i - 1][j - w[i] + B],否则不存在
if (j - w[i] >= -m) f[i][j + B] |= f[i - 1][j - w[i] + B];
if (j + w[i] <= m) f[i][j + B] |= f[i - 1][j + w[i] + B];
}
int res = 0;
for (int j = 1; j <= m; j ++ )
if (f[n][j + B])//从所有的砝码(n)中取,能够称出的所有的正整数(1-m)有那些
res ++ ;
cout<<res;
return 0;
}