【关键词】
- (DP)
- 排序/贪心
【分析】
首先，一个很明显的贪心思路，就是吃的慢的人先打饭。所以把数据按吃饭时间从大到小排一遍序。
根据(dp)的尿性，比较容易想到一个(dp)方程(f[i][j][k])：前(i)个人，在一号窗口打饭总时间为(j)，在二号窗口打饭总时间为(k)的最早集合时间。
然后转移。。。
从方程中就可以看出，这爆空间了啊。
所以优化。
我们可以发现，(j+k=)前(i)个人打饭时间总和，所以(k=sum(i)-j)，所以维护下打饭时间的前缀和就行了，于是，我们就可以去掉一维：
f[i][j]表示前i个人，在一号窗口打饭总时间(j)，最早集合的时间。
那么每次转移有两种决策。
- 将第(i)个人放在一号窗口，即： (max(f[i-1][j-s[i].wait], j+s[i].eat))
- 将第(i)个人放在二号窗口，即： (max(f[i-1][j], sum[i]-j+s[i].eat))
然后取个最小值，输出，完事。
【Code】
//#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("O2")
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define debug() puts("FBI WARNING!")
#define R register
#define I inline
using namespace std;
const int MAX = 200 + 5;
inline int read(){
int f = 1, x = 0;char ch;
do { ch = getchar(); if (ch == '-') f = -1; } while (ch < '0'||ch>'9');
do {x = x*10+ch-'0'; ch = getchar(); } while (ch >= '0' && ch <= '9');
return f*x;
}
int n, sum[MAX], f[MAX][MAX * MAX], ans = 0x7ffffff;
struct sakura {
int eat, wait;
}sak[MAX];
inline bool cmp(const sakura &a, const sakura &b) {
return a.eat > b.eat;
}
int main(){
n = read();
for (R int i = 1;i <= n; ++i) {
sak[i].wait = read(), sak[i].eat = read();
}
memset(f, 127, sizeof (f));
f[0][0] = 0;
sort(sak + 1, sak + 1 + n, cmp);
for (int i = 1;i <= n; ++i) sum[i] = sum[i - 1] + sak[i].wait;
for (int i = 1;i <= n; ++i) {
for (int j = 0;j <= sum[i]; ++j) {
if (j >= sak[i].wait) {
f[i][j] = min(f[i][j], max(f[i-1][j-sak[i].wait], j+sak[i].eat));
}
f[i][j] = min(f[i][j], max(f[i-1][j], sum[i]-j+sak[i].eat));
}
}
for (int i = 0;i <= sum[n]; ++i) {
ans = min(ans, f[n][i]);
}
printf("%d", ans);
return 0;
}