[ZJOI2005]午餐——贪心+dp

题面传送门

首先,我们能发现一个比较显然的贪心,就是按照他们的吃饭时间从大到小排序,让吃的慢的现在前面,因为打饭的时候无论长短一定是要被计算到答案里的,但是吃饭时间却可以在打饭时同时进行,那我门肯定是想要让打饭时间内,吃饭的时间最多。 而且打饭一个时间,最多能进行俩个人(俩窗口),而吃饭却能多人同时进行。

我们可以假设只有一个队时

只有两个人甲乙;

     打饭时间      吃饭时间

甲      X             Y

乙      Z            Y+k

(k>0)如果甲先打,哪么tot(总时间)=X+Z+Y+k(因为Y+k>k);

如果乙先打,时间有两种可能:

tot=Z+Y+k(k>X);

tot=Z+X+Y(X>k);

都小于甲先打的时间;

所以可以这样交换乙先打一定更优;

然后就是愉快的dp了,我们设dp[i][j]表示前i个人,在第一个窗口排队排了j分钟的最少吃完饭时刻。

但我们有两个窗口啊,只知道第一个窗口有啥用,我们知道前i个人排队时间是一定的啊,那我们预处理前i个人排队时间的前缀和,每次减一下j不就是在第二个窗口排队的时间了吗。

两个转移,一个是第i个人去到第1个窗口,一个是第i个人去到第2个窗口。

最后枚举一下j取个min就行了。

(转移方程在代码了,并且有详解)

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#include<set>
#define N 210
#define ri register int
using namespace std;
template <class T> void in(T &x) {
    x=0;
    bool flag=0;
    char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-')
            flag=1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    if(flag)
        x=-x;
}
int dp[N][N*N];
int n;
int sum[N];
struct node {
    int x,y;
} a[N];
inline bool cmp(node a,node b) {
    return a.y>b.y;
}
int main() {
    in(n);
    for(ri i=1; i<=n; ++i)
        in(a[i].x),in(a[i].y);
    sort(a+1,a+n+1,cmp);
    for(ri i=1; i<=n; ++i)
        sum[i]=sum[i-1]+a[i].x;
    memset(dp,0x3f,sizeof dp);
    dp[0][0]=0;
    for(ri i=1; i<=n; ++i)
        for(ri j=0; j<=sum[i]; ++j) {
            if(j>=a[i].x)
                dp[i][j]=min(dp[i][j],max(dp[i-1][j-a[i].x],j+a[i].y));//当前这个i如果放在1号串口的话,当前就变成了有至少j的时间在1号排队,再加上他的吃饭时间就是他对dp[i][j]的影响,然后和只放了前i-1个,没放第i个的最小时间取一下max。
            if(sum[i]-j>=a[i].x)
                dp[i][j]=min(dp[i][j],max(dp[i-1][j],sum[i]-j+a[i].y));//二号窗口同理,只不过至少在二号窗口的排队时间变成了sum[i]-j.
        }
    int ans=233333333;
    for(ri i=0; i<=sum[n]; ++i)
        ans=min(ans,dp[n][i]);
    printf("%d",ans);
}

发表于 2018-09-11 22:00:14 in 题目