NC19158 失衡天平（背包）

题意

终于Alice走出了大魔王的陷阱，可是现在傻傻的她忘了带武器了，这可如何是好???这个时候，一个神秘老人走到她面前答应无偿给她武器，但老人有个条件，需要将所选武器分别放在天平的两端，若天平平衡则可以将天平上的所有武器拿走，还好这个天平锈迹斑斑，只要两端重量相差小于等于m就会保持平衡，Alice傻傻的认为越重的武器越好，求Alice最多能拿走的武器总重量。（不限操作次数）
其中， $n,m,a_i\leq 100$ 。

分析

这题还是比较简单滴。
首先，容易发现，称多次和称一次没有区别，也就是称一次就可以得到最终的答案。假如你称两次，第一次为 $(x_1,y_1)$ ，第二次为 $(x_2,y_2)$ ，其中 $x_1\leq y_1,x_2\leq y_2$ ，那么我们完全可以变成称一次 $(x_1+y_2,x_2+y_1)$ ，使得最终答案不变。所以称多次最后都可以变成称一次。
然后由于最终的限制条件是差值，我们令 $f_{i,j}$ 表示前 $i$ 个物品，大的减小的差值为 $j$ 的最大武器重量。
转移分三种：

武器太辣鸡了，不取
把武器加入小的那边
把武器加入大的那边

然后由于差值可能是负数，我们要给他加上一个大整数。
最终复杂度是 $O(n^2m)$ 的。

代码如下

#include <bits/stdc++.h>

using namespace std;

int read(){
    int x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}

const int N = 105, maxn = 20000;
int f[N][N * N * 5];

int main(){
    int i, j, k, n, m, ans = 0;
    n = read(); m = read();
    memset(f, 0xc0, sizeof(f));
    f[0][maxn] = 0;
    for(i = 1; i <= n; i++){
        k = read();
        for(j = -10000; j <= 10000; j++){
            f[i][j + maxn] = max(f[i - 1][j + k + maxn], f[i - 1][j - k + maxn]) + k;
            f[i][j + maxn] = max(f[i][j + maxn], f[i - 1][j + maxn]);
        }
    }
    for(i = -m + maxn; i <= m + maxn; i++) ans = max(ans, f[n][i]);
    printf("%d", ans);
    return 0;
}