蓝桥杯每日真题之砝码称重（01背包）

题面来源

2021年蓝桥省赛第一场G题

题面连接：http://acm.mangata.ltd/p/P1482

考点

01背包，动态规划

视频讲解

https://www.bilibili.com/video/BV1bY4y1s7J3/

思路

我们定义 f [ i ] [ j ] f[i][j] f[i][j] 表示的是前 i i i 个物品中是否能称出重量为 j j j 的砝码，由于天平是两边都能添加砝码的，于是我们对于右边的来说如果右边的重量大于左边的，我们记为正，反之我们记为负，于是我们对于每一个砝码可以放在左边（权值为负），也可以放在右边（权值为正），也可以不放，那么我们不难得到状态转移：

f [ i ] [ j ] = f [ i − 1 ] [ j ]   ∣ ∣   f [ i − 1 ] [ j − a [ i ] ]   ∣ ∣   f [ i − 1 ] [ j + a [ i ] ] f[i][j] = f[i-1][j] \ || \ f[i-1][j-a[i]] \ || \ f[i-1][j + a[i]] f[i][j]=f[i−1][j] ∣∣ f[i−1][j−a[i]] ∣∣ f[i−1][j+a[i]]

中间是 或 起来的，因为我们能从这三个状态转移过来，注意的是由于 j − a [ i ] j-a[i] j−a[i] 是可能会得到负数的，那么对于负数的情况我们其实得到的重量就是他的绝对值，于是我们给它加上绝对值

f [ i ] [ j ] = f [ i − 1 ] [ j ]   ∣ ∣   f [ i − 1 ] [ a b s ( j − a [ i ] ) ]   ∣ ∣   f [ i − 1 ] [ j + a [ i ] ] f[i][j] = f[i-1][j] \ || \ f[i-1][abs(j-a[i])] \ || \ f[i-1][j + a[i]] f[i][j]=f[i−1][j] ∣∣ f[i−1][abs(j−a[i])] ∣∣ f[i−1][j+a[i]]

代码

#include
using namespace std;
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair
#define INF 0x3f3f3f3f

const int N = 1e2+10,M = 1e5+10;

int n,a[N],f[N][M];

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	int m = 0;
	for(int i = 1;i >a[i],m += a[i];
	f[0][0] = 1;
	for(int i = 1;i = 0; --j)
			f[i][j] = f[i-1][j] || f[i-1][abs(j-a[i])] ||f[i-1][j + a[i]];
	int ans = 0;
	for(int i = 1;i