试题 历届真题 砝码称重【第十二届】【省赛】【B组】

https://blog.csdn.net/weixin_51176105/article/details/120300204 可谓之01背包变种 注意此处其实是在赋值false true

#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long ll;
const int N =2e5+20;
ll n,m,k;
struct cmp {
	bool operator()(const int&a,const int&b) const {
		return a>b;
	}
};
int P = N/2; 
bool dp[105][200010];
int w[105];
ll sum =0;
int main() {
	cin >> n;
	for(int i =1;i<=n;i++)
	{
		cin >>w[i];
		sum+=w[i];
	}
	memset(dp,0,sizeof(dp));
	dp[0][P]=1;
	for(int i =1;i<=n;i++){
		for(int j =-sum;j<=sum;j++){
			dp[i][j+P]=dp[i-1][j+P];
			if(j-w[i]>=-sum) dp[i][j+P]|=dp[i-1][j+P-w[i]];
			if(j+w[i]<=sum) dp[i][j+P]|=dp[i-1][j+P+w[i]];
			//if(j-w[i]>=-sum) dp[i][j+P]=max(dp[i][j+P],dp[i-1][j+P-w[i]]);
			//if(j+w[i]<=sum) dp[i][j+P]=max(dp[i][j+P],dp[i-1][j+P+w[i]]);
		}
	}
	int ans = 0;
	for(int i =1;i<=sum;i++){
		if(dp[n][i+P]) ans++;
	}
	cout <<ans;
	return 0;
}
//3
//1 4 6