砝码称重【第十二届蓝桥杯】【省赛】【B组】

链接：http://lx.lanqiao.cn/problem.page?gpid=T2893

题意：给你一个天平和n个砝码,每个砝码重量为ai（i=1,2,3,...），问能称出多少种不同的重量。100%样例中，1<=n<=100,sum<=1e5,sum为n个砝码总重。

思路：动态规划。线性dp，这是一个有限制的选择，所以可以看成背包问题。每个物品（砝码）都有三种状态（选择方式），1.不选；2.选，放左边；3.选，放右边。令左边权值为正，右边为负。

分析：先写出状态转移方程：dp[i][j]——前i个物品是否能称出重量j，能，dp[i][j]=1;不能dp[i][j]=0，分析转移过程：

1、不选第i个物品——dp[i][j]=dp[i-1][j]；我们不选第i个物品就能称出j重量，说明在用到n-1个物品就可以称出重量j，所以由dp[i-1][j]转移过来。

2、选，放左边——dp[i][j]=dp[i-1][abs(j-a[i])];因为令左边权值为正相当于我们要称出j重量还需要减一个重量为a[i]的,所以由dp[i-1][abs(j-a[i])]转移过来，因为j-a[i]可能为负数，防止数组越界要取绝对值。

3、选，放右边——dp[i][j]=dp[i-1][j+a[i]];同理，放右边相当于减去了一个a[i]重量，相当于我们要称出j重量要加上一个重量为a[i]的物品，所以由dp[i-1][j+a[i]]转移过来。

注意：第一个物品肯定可以称出来，所以初始化dp[1][a[1]]=1。dp[i][a[i]]=1,很容易理解，前i个物品只在天平一端放重为a[i]的砝码,那不就可以称出重量为a[i]的物品。

#include<bits/stdc++.h>
using namespace std;
int dp[105][100006]; 
int a[105];     
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n,sum=0;
	int ans=0;
	cin >> n; 
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		sum += a[i];         
	}
	dp[1][a[1]] = 1; 
	for(int i = 2; i <= n; i++) {
		int tmp = a[i];      
		for(int j = 1; j <= sum; j++) {//相当于不选第i个 
			dp[i][j] = dp[i-1][j]; 
		}
		dp[i][tmp] = 1;        
		for(int j = 1; j <= sum; j++) {
			if(dp[i-1][j]) { //如果前i-1个砝码能称出重量j 
				//分左右放 
				dp[i][j+tmp] = 1;
				dp[i][abs(j-tmp)] = 1;  
			}
		}
	}
	for(int i = 1; i <= sum; i++) //遍历判断n个砝码是否能称出重量i 
		if(dp[n][i]) ans++;
	cout << ans << endl;
	return 0;
}