试题 历届真题 砝码称重（保姆分析）

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

. 试题 G: 砝码称重 【问题描述】 你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1, W2, · · · , WN。 请你计算一共可以称出多少种不同的重量？ 注意砝码可以放在天平两边。 【输入格式】 输入的第一行包含一个整数 N。 第二行包含 N 个整数：W1, W2, W3, · · · , WN。 【输出格式】 输出一个整数代表答案。 【样例输入】 3 1 4 6 【样例输出】 10 【样例说明】 能称出的 10 种重量是：1、2、3、4、5、6、7、9、10、11。 1 = 1； 2 = 6 − 4 (天平一边放 6，另一边放 4)； 3 = 4 − 1； 4 = 4； 5 = 6 − 1； 6 = 6； 7 = 1 + 6； 9 = 4 + 6 − 1； 10 = 4 + 6； 11 = 1 + 4 + 6。 分析：开始我还想采用递归，我的天写写画画，放弃告终，看了其他文章，发现使用dp，对于一个小白来说，看到dp就紧张，最后看了一下发现我还是能够理解的（废话，纯属记录生活） 通过状态逐渐向下，首先要知道，定义了两个数组：dp[i][a[j]],a[j],a[j]表示的是重量，dp中的i表示第几个状态，如果有此重量我们给dp[i][a[j]]赋值为1；如列子，第一个状态就是1， 第二个状态是加入4，然后加减：1+4，4-1，那么第二个状态就有：1，4 ，5 ，3 那么第三个状态加入6：就有1-6，1+6，4-6，4+6，5+6，5-6，3-6，3+6还要继承上一状态 因为我们是赋值1嘛重复时也不怕：所以第三状态为：1到10 废话不多说， 附上代码：

#include<iostream>
#include<algorithm>
using namespace std;
int dp[110][10006] = {
          
   0};
int a[110];
int main()
{
          
   
	//采用dp算法
	int n,sum=0,ans=0;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
          
   
		cin >> a[i];
		sum += a[i];
	}
	
	//开始dp状态逐渐转移
	//第一个状态a[1]是肯定存在的
		dp[1][a[1]] = 1;//i表示第几个状态，a[j]表示重量
	for (int i = 2; i <= n; i++)//其他状态，继承状态
	{
          
   
		int x = a[i];//把值赋给x便于编写
		for (int j = 1; j <= sum; j++)//把上一个状态赋给当前状态
			//主要是看存在1的dp
		{
          
   
			dp[i][j] = dp[i - 1][j];
		}
		dp[i][x] = 1;//传入当前数的状态
		for (int j = 1; j <= sum; j++)//开始加减传入数
		{
          
   
			if (dp[i-1][j] == 1)//如果执行时有数子的才进行加减
			{
          
   
				dp[i][j + x] = 1;//加法
				dp[i][abs(j - x)] = 1;//减法
			}

		}
	
	
	}
	for (int j = 1; j <= sum; j++)
	{
          
   
		if (dp[n][j] == 1)
		{
          
   
			ans++;
		}
	}
	cout << ans << endl;
}

运行代码：