链接: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;
}