[ZJOI2005]午餐（dp，贪心）

发表于 更新于 分类于 ， ，
ZJOI2005

题目

描述

上午的训练结束了，THU ACM小组集体去吃午餐，他们一行N人来到了著名的十食堂。这里有两个打饭的窗口，每个窗口同一时刻只能给一个人打饭。由于每个人的口味（以及胃口）不同，所以他们要吃的菜各有不同，打饭所要花费的时间是因人而异的。另外每个人吃饭的速度也不尽相同，所以吃饭花费的时间也是可能有所不同的。

THU ACM小组的吃饭计划是这样的：先把所有的人分成两队，并安排好每队中各人的排列顺序，然后一号队伍到一号窗口去排队打饭，二号队伍到二号窗口去排队打饭。每个人打完饭后立刻开始吃，所有人都吃完饭后立刻集合去六教地下室进行下午的训练。

现在给定了每个人的打饭时间和吃饭时间，要求安排一种最佳的分队和排队方案使得所有人都吃完饭的时间尽量早。

假设THU ACM小组在时刻0到达十食堂，而且食堂里面没有其他吃饭的同学（只有打饭的师傅）。每个人必须而且只能被分在一个队伍里。两个窗口是并行操作互不影响的，而且每个人打饭的时间是和窗口无关的，打完饭之后立刻就开始吃饭，中间没有延迟。

现在给定N个人各自的打饭时间和吃饭时间，要求输出最佳方案下所有人吃完饭的时刻。

输入

第一行一个整数N，代表总共有N个人。

以下N行，每行两个整数 Ai，Bi。依次代表第i个人的打饭时间和吃饭时间。

输出

一个整数T，代表所有人吃完饭的最早时刻。

输入样例

1
2
3
4
5
6
5
2 2
7 7
1 3
6 4
8 5

输出样例

1
17

说明

所有输入数据均为不超过200的正整数。

解题思路

乍一看人的顺序不定，好像无从下手，这时就需要靠贪心排一个序。
先考虑只有一个窗口的情况：画一个图（蓝色打饭时间，绿色吃饭时间）

容易发现答案是所有打饭时间之和（定值)加上虚线右边支出来的一截的最大长度，所以我们要尽量让支出来的长度小。这可以贪心实现，并且贪心策略很简单：按吃饭时间从大到小排序即可。因为吃饭时间长的就更容易支出去，理所当然的应该尽可能往前放。

所以其实一个窗口的答案是可以通过贪心排序确定下来的，那么现在题目的变数就只有两个窗口如何选择了，我们就此dp。
dp状态里，我们显然需要知道已经排到第几个人了，还要知道两个队伍的信息。综合考虑后发现，我们只需要第一个队伍总共打饭时间即可，因为哪些人去了第一个队伍并不重要，此时我们可以通过简单计算算出第二个队伍总共打饭时间，于是我们定义 $dp[i][j]$ 为前 $i$ 个人中，第一个队伍总共打饭时间为 $j$ 的最小集合时间。由此推出：

  • dp状态：$dp[i][j]$ 为前 $i$ 个人中，第一个队伍总共打饭时间为 $j$ 的最小集合时间
  • dp方程：
    $dp[i][j] = min( max(dp[i-1][j-p[i].a], j + p[i].b), max(dp[i-1][j], sum[i] - j + p[i].b) );$
    即分别考虑第 $i$ 个去第一个还是第二个窗口。$sum[i]$ 表示前 $i$ 个人的总共打饭时间
  • dp顺序：由转移方程可得：依次for i = 1 to n，for j = 0 to sum[i] 即可
  • 边界条件：$dp[0][0] = 0$，其他初始状态为INF

时间复杂度：$O(N^3)$

Code

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
# include<bits/stdc++.h>

using namespace std;

//此处省略了 define 的一些东西和输入输出优化

const int N = 205;
const int INF = 1e9;

int n, dp[N][N*N], sum[N], ans = INF;

struct Person{
	int a, b;
}p[N];
bool cmp(Person x, Person y){ return x.b > y.b; }

int main(){
	in(n);
	fo1(i, 1, n){
		in(p[i].a);
		in(p[i].b);
	}
	sort(p+1, p+n+1, cmp);
	mset(dp, 0x3f);
	dp[0][0] = 0;
	fo1(i, 1, n){
		sum[i] = sum[i-1] + p[i].a;
		fo1(j, 0, sum[i]){
			if(j >= p[i].a)	dp[i][j] = min(dp[i][j], max(dp[i-1][j-p[i].a], j + p[i].b));
			dp[i][j] = min(dp[i][j], max(dp[i-1][j], sum[i] - j + p[i].b));
		}
	}
	fo1(i, 0, sum[n])	ans = min(ans, dp[n][i]);
	outln(ans);
	return 0;
}