洛谷 P2577 [ZJOI2005]午餐

首先吃饭时间长的排在前面更优，所以先排个序

然后问题就是怎么分配这一波人的问题

刻画状态有人和时间，然后分两队

所以用 $f[i][j][k]$ 表示前i个人，第一队用j时间，第二队用k时间的最小吃饭时间

那么因为这么开数组会炸，所以我们要降一维。

前i个人的等待总时间是固定的，所以第二队的时间可以推出来

那么接下来就是非常非常关键的状态转移方程了

$f[i][j] = min(max(f[i-1][j-t], j + p))$

$f[i][j] = min(max(f[i-1][j], s[i] - j + p))$

t是当前人的打饭时间，p是当前人的吃饭时间

第一个方程是把当前人分到第一队中去。

$f[i-1][j-t]$ 表示前i-1个人的最晚吃饭时间， $j + p$ 是第i个人的吃饭时间

取max即可

第二个方程同理， $s[i] - j$ 表示第二队当前的时间

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++) 
#define _for(i, a, b) for(int i = (a); i <= (b); i++) 
using namespace std;

const int MAXN = 212;
int f[MAXN][MAXN*MAXN], s[MAXN], n;
struct node
{
	int t, p;
	bool operator < (const node& rhs) const
	{
		return p > rhs.p;
	}
}a[MAXN];

void read(int& x)
{
	int f = 1; x = 0; char ch = getchar();
	while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
	while(isdigit(ch)) { x = (x << 3) + (x << 1) + ch - '0'; ch = getchar(); }
	x *= f;
}

int main()
{
	read(n);
	_for(i, 1, n) read(a[i].t), read(a[i].p);
	sort(a + 1, a + n + 1);
	_for(i, 1, n) s[i] = s[i-1] + a[i].t;
	
	int ans = 1e9;
	memset(f, 0x3f, sizeof(f));
	f[0][0] = 0;
	
	_for(i, 1, n)
		_for(j, 0, s[i]) 
		{
			int t = a[i].t, p = a[i].p;
			if(j >= t) f[i][j] = min(f[i][j], max(f[i-1][j-t], j + p));
			f[i][j] = min(f[i][j], max(f[i-1][j], s[i] - j + p));
			if(i == n) ans = min(ans, f[i][j]);
		}
	printf("%d
", ans);
	
	return 0;
}