Description
一共 (n) 个人去打饭，每个人一个打饭时间 (A_i)、吃饭时间 (B_i)。要求把 (n) 个人分成两组，每组占领一个窗口不间断打饭，最小化所有人吃完饭时刻。
Solution
首先这是一个排列数问题，与 AcWing 734. 能量石 类似，不妨用贪心尝试将排列数问题转化为组合数问题。
贪心
我们先之考虑一队同学，尝试用微扰的方式证明一下。
假设两个人 (i, j) 在一队按顺序打饭，设前面人打完饭的时刻是 (t)，他们对答案的贡献是：
将 (i, j) 颠倒顺序，他们的贡献是：
两项交换不会使答案贡献更优：
整理一下得：
由于所有数是正整数，所以 (a[i] + a[j] + b[j] > a[j] + b[j])，(a[j] + a[i] + b[i] > a[i] + b[i])。
所以 (max) 函数的第一项不可能作为四个值的最大值，把它消去：
移项：
所以，我们把所有人按 (b) 从大到小排序，枚举的最优解一定是两个序列，每队从新下标的顺序从小到大排队。
DP
现在排列问题变成了组合问题，我们就可以 DP 了。
我们需要知道信息有：
-
是两个队列最后一个人打完饭的时刻。
-
最早时刻（答案）
设计状态
首先想到：
- 设 (f_{i, j, k}) 为前 (i) 个人，两队最后一个人打完的时刻分别为 (j, k)，吃完饭的最早时刻。
但是空间过大，考虑降维，显然 (j + k = sum_{u = 1}^{i} a[i])，所以再维护一个 (a) 的前缀和，那么已知 (i, j) 可以 (O(1)) 推出 (k)
设 (f_{i, j, k}) 为前 (i) 个人，其中一队最后一个人打完的时刻分别为 (j)，吃完饭的最早时刻。
初始状态
(f_{0, 0} = 0)，其余为正无穷。
状态转移
还是喜欢我为人人，符合人类的正常思维。
当前状态是 (f_{i, j})，将另一队的时刻 (k) 求出来，考虑第 (i + 1) 个人分配到哪个队伍。
-
分配到 (j) 这个队伍，(f_{i + 1, j + a[i + 1]} = min{ max(f_{i, j}, j + a[i + 1] + b[i + 1]) })
-
分配到另一个队伍，(f_{i + 1, j} = min{ max(f_{i, j}, k + a[i + 1] + b[i + 1]) })
答案
( ext{Ans} = min(f[n][i]))
时间复杂度
(O(N^3))
代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 205, INF = 0x3f3f3f3f;
int n, a[N], b[N], s[N], f[N][N * N];
struct E{
int a, b;
bool operator < (const E &x) const {
return b > x.b;
}
} e[N];
void inline update(int &x, int y) {
if (x > y) x = y;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d", &e[i].a, &e[i].b);
sort(e + 1, e + 1 + n);
for (int i = 1; i <= n; i++) s[i] = s[i - 1] + e[i].a;
memset(f, 0x3f, sizeof f);
f[0][0] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= s[i]; j++) {
if (f[i][j] == INF) continue;
int k = s[i] - j;
update(f[i + 1][j + e[i + 1].a], max(f[i][j], j + e[i + 1].a + e[i + 1].b));
update(f[i + 1][j], max(f[i][j], k + e[i + 1].a + e[i + 1].b));
}
}
int ans = INF;
for (int i = 0; i <= s[n]; i++) ans = min(ans, f[n][i]);
printf("%d
", ans);
return 0;
}