题目分析
原题链接 P8742 [蓝桥杯 2021 省 AB] 砝码称重
由这道题，我们不难联想到 P2347 砝码称重，两题的做法是相似的。因此这道题做法就是背包。
其本质上都是选取砝码，求能表示的重量的个数。
而这道题特别的地方在于多了个天平，因此左右两盘就意味着砝码可以“相减”，状态转移的时候需要注意。
由于本体是可行性问题，因此我们设 \(dp_{i,j}\) 为选取前 i 个砝码是否可以称量出 j 的重量。\(dp_{i,j} =1\) 表示能，\(dp_{i,j} =0\) 表示不能。
接下来考虑转移：
若 \(dp_{i-1,j}=1\)，那么：
-
\(dp_{i,j}\) 是可行的，因为可以不选第 i 个砝码；
-
\(dp_{i,j+a_i}\) 也是可行的，显然；
当涉及到 \(dp_{i,j-a_i}\) 的转移时， \(j-a_i\) 有可能为负值，但并不影响转移。因为天平左右盘可以互换，所以本质上等价于 \(a_i-j\) 。
例如：样例中状态至 \(dp_{3,2}\) 时，可以由状态 \(dp_{2,4}\) 转移而来，即左盘放重量为 4 的砝码，右盘放重量为 6 的砝码。
- \(dp_{i,|j-a_i|}\) 也是可行的
AC Code
#include<stdio.h>
using namespace std;
const int N=105,M=1e5+5;
int ans,n,dp[N][M];
inline int read(){
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int abs(int x){return x>0?x:-x;}
int main(){
n=read();
dp[0][0]=1;
for(int i=1;i<=n;i++){
int a=read();
for(int j=0;j<=100000;j++){
dp[i][j]|=dp[i-1][j];
dp[i][j+a]|=dp[i-1][j];
dp[i][abs(j-a)]|=dp[i-1][j];
}
}
for(int i=1;i<=100000;i++) if(dp[n][i]) ans++;
printf("%d",ans);
return 0;
}