洛谷 P2577 [ZJOI2005]午餐 题解【贪心】【DP】

点击量：216

    不是很熟悉但是很有用的DP转移

目录

题目描述

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

 

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

 

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

 

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

 

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

 

输入输出格式

输入格式：

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

 

以下\(N\)行，每行两个整数\(A_i,B_i\)。依次代表第\(i\)个人的打饭时间和吃饭时间。

 

输出格式：

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

 

输入输出样例

输入样例#1：

5
2 2
7 7
1 3
6 4
8 5

输出样例#1：

17

说明

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

题解：

    首先这个题需要用贪心来将每个人排序，否则无法进行唯一的DP。但是贪心会有两个思路，分别是按吃饭时间降序排序，和按打饭+吃饭时间之和降序排序，因为我们要避免吃饭时间长的人后打饭。

    设第\(i\)个人的打饭时间为\(a_i\)，吃饭时间为\(b_i\)，令\(a_i+b_i>a_{i+1}+b_{i+1}\)（如果小于的话当然要把既满足总时间长又满足吃饭时间长的人放在前面），但\(b_i<b_{i+1}\)，则\(a_i>a_{i+1}\)。即第\(i+1\)个人的吃饭时间较长。假设只有一列队，如果将\(i\)排在前面，那么总时间为\(f_1=\max(a_i+b_i,a_i+a_{i+1}+b_{i+1})=a_i+a_{i+1}+b_{i+1}\)，因为\(a_i+b_{i+1}>a_i+b_i\)。而将\(i\)排在后面，则总时间为\(f_2=\max(a_{i+1}+a_i+b_i,a_{i+1}+b_{i+1})=a_{i+1}+a_i+b_i\) 。那我们比较\(f_1\)和\(f_2\)，\(f_1-f_2=b_{i+1}-b_i>0\)，因此\(f_1>f_2\)。所以贪心的结论是把吃饭时间长的人排在前面。

    这样可以先把每个人排序，然后就可以做一个类似背包的DP了。设f[i][j][k]表示排完了\(i\)个人，第一队结束排队时间为\(j\)，第二队结束时间为\(k\)的最早吃完饭的时间。这样直接做转移就可以了，f[i][j][k]=min(max(f[i-1][j-a[i]][k],j+b[i]),max(f[i-1][j][k-a[i]],k+b[i]))。但是这样的时间复杂度是\(O(n^5)\)，因为状态共有\(200\times 200^2\times 200^2\)个。

    考虑到时间复杂度主要由状态个数贡献，因此考虑压维。我们看到，当贪心地排序后，序列是一定的。因此\(j+k\)也就成了定值，也就是说，我们在DP数组中存下\(j\)，利用预处理的前缀和\(sum\)减去这个\(j\)，就是所求的\(k\)了。这样状态就只剩下\(n^3\)，是可以过的，相应地改一下转移方程就可以了（把\(k\)代换为\(sum[i]-j\)即可）。

    这个题的主要思维在贪心。同时较难的地方还有压掉一维，不过见得多了也许就是一种套路了吧。

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::min;
using std::max;
struct pp
{
    int x,y;
    friend bool operator <(pp a,pp b)
    {
        return a.y>b.y;
    }
}a[222];
int f[205][40005];
int main()
{
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d%d",&a[i].x,&a[i].y);
    std::sort(a+1,a+1+n);
    int tt=0;
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<=200*i;++j)
            if(j<a[i].x)
                f[i][j]=max(f[i-1][j],tt-j+a[i].x+a[i].y);
            else
                f[i][j]=min(max(f[i-1][j-a[i].x],j+a[i].y),max(f[i-1][j],tt-j+a[i].x+a[i].y));
        tt+=a[i].x;
    }
    long long ans=0x7ffffffffff;
    for(int i=0;i<=200*n;++i)
        ans=ans<f[n][i]?ans:f[n][i];
    printf("%lld\n",ans);
    return 0;
}