洛谷 P2577 [ZJOI2005]午餐

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

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

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

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

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

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

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

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

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

表示前i-1个人的最晚吃饭时间， 是第i个人的吃饭时间

取max即可

第二个方程同理，表示第二队当前的时间

#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\n", ans);return 0;
}