蓝桥杯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
using namespace std;
const int N = 1e5+10;
const int Bais = N;

int n, a[N], ans, m;
bool f[110][N  n;
	for (int i = 1;i > a[i], m += a[i];
	
	f[0][Bais] = true; // 用0个砝码称出重量为0的物品 
	for (int i = 1;i