[ZJOI2005]午餐

Link
两个窗口不是很好想，那么首先我们需要确定一个窗口内的打饭顺序。
考虑对于一个窗口的所有人，假设这些人不变，那么不管这个窗口的人的排列是怎么样的，其打饭的时间永远都是所有排队的人的打饭时间的和，那么，但是我们仍然需要考虑所有人打完饭之后仍然会有人在吃饭的问题，于是考虑将吃饭时间长的人排在前面。如何解释想必不用我说了，这种东西稍微想一想应该是可以明白的。
那么首先的算法确定为一个贪心的排序处理，按照吃饭时间从大到小排序。
之后我们要考虑的就是谁在1号窗口，谁在二号窗口，这个DP数组应该还是比较好想的，一般来说首先想到的的就是一个三位数的数组$F[i][j][k]$,表示前i个人，j个人在1号窗口，k个人在2号窗口吃完饭的最早时间。
而显然我们可以看到k = i - j，于是我们省下来一维。
然后怎么转移呢，首先可以考虑维护一个打饭时间前缀和Sum[]，对于第i个人，只有两种方案可以转移，就是1号窗口和2号窗口，分别是这样的：

$$Dp[i][j] = min(Dp[i][j], max(Dp[i - 1][j - E[i].X], j + E[i].Y)) ;$$

这个玩意是什么意思呢？
就是说，我们在这个转移之中需要考虑第i个人和第i - 1个人的打饭和吃饭时间。
目前，第i - 1个人刚刚打完饭去吃饭，然后第i个人来打饭，打完饭之后吃饭，然后这两个人的回合结束，那么结束时间以谁为准呢？
当然是时间长的那个，那么我们那就比较第i - 1个人的吃饭时间，和第i个人的打饭时间+吃饭时间，取最优。
对于上面那个式子，$Dp[i][j] = Dp[i - 1][j - E[i].X]$时就是说i - 1赢过了i，那么就没有任何影响，但是当$Dp[i][j] = j + E[i].Y$的时候代表i赢过了i - 1，于是需要相应的变换。
然后我们如上就等到第二号窗口的状态转移方程：

$$Dp[i][j] = min(Dp[i][j], max(Dp[i - 1][j], Sum[i] - j + E[i].Y)) ;$$

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

typedef long long LL ;
const int MAXN = 210 ;
const int MAXM = 210 ;
const int INF = 0x7fffffff ;
int N, Tot1, Tot2, Sum[MAXN], Dp[MAXN][MAXN * MAXM], Ans = INF ;
struct Person {
	int X, Y ;
}	E[MAXN] ;

inline int Read() {
	int X = 0, F = 1 ; char ch = getchar() ;
	while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
	while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
	return X * F ;
}

inline bool CMP(Person A, Person B) {
	return A.Y > B.Y ;
}

int main() {
	N = Read() ;
	for (int i = 1 ; i <= N ; i ++) E[i].X = Read(), E[i].Y = Read() ;
	sort(E + 1 , E + N + 1, CMP) ;
	for (int i = 1 ; i <= N ; i ++)
		Sum[i] = Sum[i - 1] + E[i].X ;
	memset(Dp, 127, sizeof(Dp)) ;
	Dp[0][0] = 0 ;
	for (int i = 1 ; i <= N ; i ++)
	for (int j = 0 ; j <= Sum[i] ; j ++) {
		if (j >= E[i].X) Dp[i][j] = min(Dp[i][j], max(Dp[i - 1][j - E[i].X], j + E[i].Y)) ;
		Dp[i][j] = min(Dp[i][j], max(Dp[i - 1][j], Sum[i] - j + E[i].Y)) ;
	}
	for (int i = 0 ; i <= Sum[N] ; i ++)
		Ans = min(Ans, Dp[N][i]) ;
	printf("%d\n", Ans) ;
	return 0 ;
}