[ZJOI2005] 午餐

分析

DP& 贪心

首先贪心地想到,让吃饭时间长的先排队(邻项微扰证明)

定义 表示前 i 个人,1 号窗口打饭总时间为 时的最早吃完饭的时间。

  • 当第 个人在 1 号窗口时,吃完饭的时间为 包含了 2 号窗口吃完饭的时间,而 表示第 个人吃完饭的时间,两者取最大值。
  • 同理,当第 个人在 2 号窗口时,吃完饭时间为 . 求和的部分用前缀和优化即可。
  • 初始化 INF, .
  • 答案即 .

代码

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=203;
int n,f[N][N*N];// 前 i 个人,在 1 窗口打饭时间为 j 的最早吃完饭的时间
int ps[N];//pre_sum

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

int main(){scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&d[i].a,&d[i].b);
    sort(d+1,d+n+1,cmp);
    for(int i=1;i<=n;i++)ps[i]=ps[i-1]+d[i].a;// 前缀和
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    for(int i=1;i<=n;i++){for(int j=0;j<=ps[i];j++){f[i][j]=max(f[i-1][j],ps[i]-j+d[i].b);//j 在 2 窗
            if(j>=d[i].a)f[i][j]=min(f[i][j],max(f[i-1][j-d[i].a],j+d[i].b));
        }
    }
    int ans=0x3f3f3f3f;
    for(int i=0;i<=ps[n];i++)ans=min(ans,f[n][i]);
    printf("%d",ans);
    return 0;
}

  转载请注明: Sshwy's Blog [ZJOI2005] 午餐

 上一篇
[AHOI2009] 中国象棋 [AHOI2009] 中国象棋
分析计数 DP 三进制状压 DP 可以拿 50 分 考虑到我们并不需要记录每一列的相对位置 定义 表示前 行中有 列放了 1 个棋子, 列放 2 个棋子的方方案数 采用刷表法,对于 $f[i,j,
2018.11.18
下一篇 
[ZJOI2007] 棋盘制作 [ZJOI2007] 棋盘制作
悬线法。以每一个点向上达到的最长的长度作为悬线,左右扫,记录可以到达的最左边的长度以及最右边的长度,再以此更新答案即可。 更具体的, 表示从 往上最长的黑白相间的格子的高度; 表示从
2018.11.17
  目录