题目描述
https://www.luogu.com.cn/problem/P2577
Solution
我们令 $f[i][j]$ 表示前 $i$ 个人，第一队的打饭总时间为 $j$ 的最短时刻
注意到打饭总时间是固定的，假设在只有一队的情况下，我们一定是让吃饭时间长的人排在前面
如果有两队的话，由于我们 $dp$ 是决定每个人放到一队还是二队，所以必须要在 $dp$ 之前进行排序
时间复杂度 $O(200^3)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 210
#define maxm 40010
#define cn const node
#define INF 1000000000
using namespace std;
int n;
struct node {
int x, y;
friend bool operator < (cn &u, cn &v) { return u.y > v.y; }
} a[maxn];
int f[maxn][maxm];
void memset_f() {
for (int i = 0; i < maxn; ++i)
for (int j = 0; j < maxm; ++j) f[i][j] = INF;
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i].x >> a[i].y;
sort(a + 1, a + n + 1); int sum = 0;
memset_f(); f[0][0] = 0;
for (int i = 1; i <= n; sum += a[i++].x)
for (int j = 0; j <= sum; ++j) {
f[i][j] = min(f[i][j], max(f[i - 1][j], sum - j + a[i].x + a[i].y));
f[i][j + a[i].x] = min(f[i][j + a[i].x], max(f[i - 1][j], j + a[i].x + a[i].y));
}
int ans = INF;
for (int i = 0; i <= sum; ++i) ans = min(ans, f[n][i]);
cout << ans << endl;
return 0;
}
|