NC19158 失衡天平

题目地址：

https://ac.nowcoder.com/acm/problem/19158

基本思路：

这道题我们首先要证明一件事情，就是最终能被拿走的武器总重量一定是能在一次内拿走的。

本来想证明一下，可是发现自己太菜了好像证不来QAQ，但是多带几个数据并且脑补一下基本上还是能确定这个结论的正确性的。

那么接下来就是思路比较清晰的 $dp$ ，我们设 $dp[i][j]$ 表示加到第 $i$ 个物品，左右物品间的绝对差是 $j$ ，那么对于每个物品我们就有不加入，加入左边，加入右边这三种状态。

那么根据以上容易得到转移方程: $dp[i][j] = max(dp[i-1][j],dp[i-1][abs(j-a[i])],dp[i-1][j + a[i]])$ 。

那么最终答案 $ans = max(ans,dp[n][i]),i\in[0,m]$ 。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int maxn = 110;
int n,m,a[maxn];
int dp[maxn][maxn * maxn];
signed main() {
  IO;
  cin >> n >> m;
  rep(i, 1, n) cin >> a[i];
  mset(dp, -0x3f3f3f3f);
  dp[0][0] = 0; //两边都不放的状态;
  int sum = 0;
  for (int i = 1; i <= n; i++) {
    sum += a[i];
    for (int j = 0; j <= sum; j++) {
      //三种情况中取最优;
      int tmp = max(dp[i - 1][abs(j - a[i])], dp[i - 1][j + a[i]]);
      dp[i][j] = max(dp[i - 1][j], tmp + a[i]);
    }
  }
  int ans = 0;
  //在绝对差属于[1,m]的范围内取最大重量;
  for (int i = 0; i <= m; i++) ans = max(ans, dp[n][i]);
  cout << ans << '\n';
  return 0;
}