题目地址：洛谷：【P2577】[ZJOI2005]午餐 – 洛谷、BZOJ：Problem 1899. — [Zjoi2004]Lunch 午餐

题目描述

上午的训练结束了，THU ACM小组集体去吃午餐，他们一行N人来到了著名的十食堂。这里有两个打饭的窗口，每个窗口同一时刻只能给一个人打饭。由于每个人的口味（以及胃口）不同，所以他们要吃的菜各有不同，打饭所要花费的时间是因人而异的。另外每个人吃饭的速度也不尽相同，所以吃饭花费的时间也是可能有所不同的。
THU ACM小组的吃饭计划是这样的：先把所有的人分成两队，并安排好每队中各人的排列顺序，然后一号队伍到一号窗口去排队打饭，二号队伍到二号窗口去排队打饭。每个人打完饭后立刻开始吃，所有人都吃完饭后立刻集合去六教地下室进行下午的训练。
现在给定了每个人的打饭时间和吃饭时间，要求安排一种最佳的分队和排队方案使得所有人都吃完饭的时间尽量早。
假设THU ACM小组在时刻0到达十食堂，而且食堂里面没有其他吃饭的同学（只有打饭的师傅）。每个人必须而且只能被分在一个队伍里。两个窗口是并行操作互不影响的，而且每个人打饭的时间是和窗口无关的，打完饭之后立刻就开始吃饭，中间没有延迟。
现在给定N个人各自的打饭时间和吃饭时间，要求输出最佳方案下所有人吃完饭的时刻。

输入输出格式

输入格式：
第一行一个整数N，代表总共有N个人。
以下N行，每行两个整数 Ai，Bi。依次代表第i个人的打饭时间和吃饭时间。

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

输入输出样例

输入样例#1：

5
2 2
7 7
1 3
6 4
8 5

输出样例#1：

17

说明

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

题解

本题是一个贪心加DP的题目。首先我们可以将题目分为两部分：排序和分配。

排序：贪心

贪心的依据是吃饭慢的先打饭。这个在我们的直觉中就是正确的，而证明也很容易。
假设队列中有两个人i和j，他们有确定关系B_i < B_j。如果按照i j这样的顺序排列，他们两个人产生的答案分别是A_i + B_i和A_i + A_j + B_j。这里显然最终答案是后者。如果按照j i的顺序排列，则变为A_j + B_j和A_j + A_i + B_i。这两个答案都不会比第一种情况的答案大。因此我们确定j i排列比i j排列更优。

分配：DP

设计状态dp[i][j]表示现在排到第i个人，第一队打饭要用j时间的吃完饭时刻。现在分情况讨论第i个人是加入第一队还是加入第二队。
加入第一队：
dp[i][j + A_i] = \max \{dp[i - 1][j], j + A_i + B_i\}
加入第二队：
dp[i][j] = \max \{dp[i - 1][j], S_i - j + B_i\}
其中S表示从第一个人到第i个人的打饭时间前缀和。
我们发现第一维数据为n，第二维是n^2，空间复杂度O(n^3)。这是可以接受的，但是仍然可以优化。
总时间复杂度：O(n^3)

优化空间：滚动数组和降维

与其他可以用这种优化空间的方法的题目相似，这里不再赘述。

代码

// Code by KSkun, 2018/2
#include <cstdio>
#include <cstring>
#include <algorithm>

struct Node {
    int a, b;
};

int n, dp[40005], sum = 0, ans = 1e9;
Node p[205];

inline bool cmp(Node a, Node b) {
    return a.b > b.b;
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d%d", &p[i].a, &p[i].b);
    }
    std::sort(p + 1, p + n + 1, cmp);
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = sum; j >= 0; j--) {
            dp[j + p[i].a] = std::min(dp[j + p[i].a], 
                std::max(dp[j], j + p[i].a + p[i].b)); // 加入第一队 
            dp[j] = std::max(dp[j], sum + p[i].a - j + p[i].b); // 加入第二队 
        }
        sum += p[i].a;
    }
    for(int i = 1; i <= sum; i++) {
        ans = std::min(ans, dp[i]);
    }
    printf("%d", ans);
    return 0;
}