蓝桥杯--砝码称重（dp）

雨点打透心脏的1/2处 2021-07-16 16:10 378阅读 0赞

## 砝码称重 ##

[题目评测][Link 1]

你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1,W2,⋅⋅⋅,WN。

请你计算一共可以称出多少种不同的正整数重量？

注意砝码可以放在天平两边。  
输入格式

输入的第一行包含一个整数 N

。

第二行包含 N  
个整数：W1,W2,W3,⋅⋅⋅,WN

输出格式

输出一个整数代表答案。  
数据范围

对于 50%  
的评测用例，1≤N≤15。  
对于所有评测用例，1≤N≤100，N 个砝码总重不超过 1e5。

## 思路 ##

很容易想到是dp，但需要注意的是对于负数的称重如何处理。  
dp\[i\]\[j\]代表前i个砝码是否可以称出j的重量,dp\[i\]\[j\]=1表示存在=0表示不存在。  
状态转移方程：当dp\[i-1\]\[j\]=1时,第i个砝码重量为a  
dp\[i\]\[j\]=1,第i个砝码不使用  
dp\[i\]\[j+a\]=1,第i个砝码和之前能称出的重量j相加  
dp\[i\]\[j-a\]=1,两相减  
dp\[i\]\[a-j\]=1,两相减  
这四个状态代表了，当前i-1个砝码能称出j重量时可以和新加入的砝码称出的四个新状态，但这个重量可能会有负数的，所以默认加上100000当作一个偏移量，最后计算结果再减去即可。

这个代码状态我优化了一下空间，思路还是一样的。  
Ac Code

#include<iostream>
    using namespace std;
    const int Max = 1e6 + 5;
    
    int dp[Max];
    int ls[Max];
    
    int main()
    { 
    	int n;cin >> n;
    	dp[100000] = 1;
    	for (int i = 1;i <= n;i++)
    	{ 
    		int a;cin >> a;
    		int g = 0;
    		for (int j = 0;j <= 200000;j++)
    		{ 
    			if (dp[j] >= 1)
    			{ 
    				ls[++g] = (j + a);
    				ls[++g] = (j - a);
    				ls[++g] = (a - j);
    			}
    		}
    		for (int j = 1;j <= g;j++)
    		{ 
    			dp[ls[j]]++;
    		}
    	}
    	int ans = -1;
    
    	for (int i = 100000;i <= 200000;i++)if (dp[i]) ans++;
    	cout << ans;
    }

## 思路二 ##

其时当发现一个重量可以得负数，再和以后的状态做加减转化时，正数减去也能代表负数，  
如 有砝码 2 1 3  
前俩可以拼凑出的状态 1 2 3 -1，  
3 + （-1）和 3 - 1 效果是一样的，所以负的重量状态抛弃掉最后结果也是不变的

化简Code

#include<iostream>
    using namespace std;
    
    int dp[105][100005];
    
    int main()
    { 
    	int n;cin >> n;
    	dp[0][0] = 1;
    	for (int i = 1;i <= n;i++)
    	{ 
    		int a;cin >> a;
    		for (int j = 0;j <= 100000;j++)
    		{ 
    			if (dp[i-1][j])
    			{ 
    				dp[i][j] = 1;
    				dp[i][j + a] = 1;
    				dp[i][abs(j - a)] = 1;
    			}
    		}
    	}
    	int ans = 0;
    	for (int i = 1;i <= 100000;i++)if (dp[n][i]) ans++;
    	cout << ans;
    }

[Link 1]: https://www.acwing.com/problem/content/description/3420/