蓝桥杯2021年第十二届真题第一场-砝码称重

题目

题目链接

题解

动态规划。

状态定义：dp[i][j]表示前i个砝码是否能称出重量为j的物品。

状态转移：对于第i个砝码，选和不选两种情况；对于选又可以分为放在左边和放在右边。

看样例，存在加和减的情况，也就是放在左边和右边的情况。我们规定放在左边用加表示，放在右边用减表示。

那么第i个砝码的全部情况为第i个砝码不放、放左边或放右边。对于重量为j的物品，如果不放第i个砝码，则dp[i][j] |= dp[i-1][j]，即若用i-1个砝码可以称出j，那么用i个砝码肯定也行；如果将第i个砝码放在左边（正），那么用i-1个砝码只需要能称出j-w[i]的物品即可，所以dp[i][j] |= dp[i-1][j-w[i]]；类似地，将第i个砝码放在右边（负），那么dp[i][j] |= dp[i-1][j+w[i]]

存在一个问题，如此定义转移方程会存在全部砝码全放在左侧或全放在右侧的情况，也就是说会出现负数作为索引的情况。

为了避免这种情况，我们让索引加上一个大数来保证索引为正值。

最后统计能称出不同重量的物品数量时，只需要让j从1变化到最大值即可，因为k表示左边-右边=k，即右边与左边之差为k；-k表示右边-左边=k，即左边与右边之差为k，本质上都是表示能称出重量为k的物品的意思。所以如果左侧的也统计则相当于统计了两遍。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int Bais = N;

int n, a[N], ans, m;
bool f[110][N << 1]; // f[i][j]表示前i个砝码是否能称出重量为j的物品 

int main()
{
	cin >> n;
	for (int i = 1;i <= n;i ++) cin >> a[i], m += a[i];
	
	f[0][Bais] = true; // 用0个砝码称出重量为0的物品 
	for (int i = 1;i <= n;i ++)
		for (int j = -m;j <= m;j ++) {
			f[i][j+Bais] |= f[i-1][j+Bais];
			if (j - a[i] >= -m) f[i][j+Bais] |= f[i-1][j-a[i]+Bais];
			if (j + a[i] <= m) f[i][j+Bais] |= f[i-1][j+a[i]+Bais];
		}	

	for (int j = 1;j <= m;j ++) ans += f[n][j+Bais];
	
	cout << ans << endl;
	return 0;
}