P8742 [蓝桥杯 2021 省 AB] 砝码称重 题解

P8742 [蓝桥杯 2021 省 AB] 砝码称重 题解

显然，考虑如何进行

设状态转移数组表示在前个砝码中，有没有组成重量为的方案。

考虑转移情况，每个状态可以由：

• 第个选了砝码在异侧

• 第个选了砝码在同侧

• 未选砝码

  转移而来

则转移方程式为

由于可能会出现在运算过程中小于零的情况，所以要将整体右移（加上一个大数）

时间复杂度（为值域），可以通过本题

空间复杂度超标，需要使用滚动数组。

标程：

#include<bits/stdc++.h>
#define ll long long
#define M 200005
#define inf 1000000007
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
int n,w[105],f[2][2*M],sm;
ll ans;
int read(){
	int res=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-'&&((ch=getchar())>='0'&&(ch)<='9')) f=-1;
		else ch=getchar();
	}
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return res*f;
}
int main(){
	n=read();
	fo(i,1,n)w[i]=read();
	f[0][M]=1;
	fo(i,1,n){
		sm+=w[i];
		fo(j,-sm,sm){
			f[i&1][j+M]=f[(i-1)&1][j+M-w[i]]|f[(i-1)&1][j+M+w[i]]|f[(i-1)&1][j+M];
		}
	}
	fo(i,1,sm){
		if(f[n&1][i+M])++ans;
	}
	printf("%lld",ans);
}