链接
难度：\(\texttt{17/21}\)
\(T\) 组数据。
有 \(n\) 组，每组有 \(2\) 个数 \(x,y\)，问把每组的一个数分配到一组另一个数分配到另一组两组数字和差的绝对值最小是多少。
数据范围：\(1\le T\le 10,1\le n\le 200,1\le x,y\le 250\)。
有点套路的题目。
首先能想到用 01 背包 \(f_{i,j}\) 代表到第 \(i\) 组，第一组数的和 \(-\) 第二组数的和差为 \(j\) 是否可行，便可得转移方程 \(f_{i,j}=f_{i-1,j-(x-y)}|f_{i-1,j+(x-y)}\)。
这样的单次时间复杂度是 \(O(2n\sum |x-y|)\)，计算量已经达到了 \(2\times 10^7\)，尝试优化。
发现 \(f_{i,j}\) 只会为 \(\texttt{0/1}\)，且操作对应的正是位移，便考虑用 bitset 优化，单次时间复杂度便为 \(O(\frac{2n\sum |x-y|}{w})\)，\(w=32/64\)。
# include <bits/stdc++.h>
using namespace std;
const int N = 200, C = 250, T = 2;
bitset <(N * C << 1) + 100> B [T]; // 有负数开 2 倍
int main () {
ios :: sync_with_stdio (false);
cin .tie (0);
cout .tie (0);
int t;
cin >> t;
while (t --) {
B [0] .reset (), B [1] .reset ();
B [0] [N * C + 10] = 1;
int n;
cin >> n;
for (int i = 1, x, y; i <= n; ++ i) {
cin >> x >> y;
int c = max (x, y) - min (x, y);
B [i & 1] = (B [(i & 1) ^ 1] >> c) | (B [(i & 1) ^ 1] << c);// 左移和右移都有
}
for (int i = 0; ; ++ i) {
if (B [n & 1] [N * C + 10 - i] || B [n & 1] [N * C + 10 + i]) {
cout << i << '\n';
break;
}
}
}
return 0;
}