洛谷 P2577 [ZJOI2005]午餐 题解

每日一题 day56 打卡

Analysis

算法:贪心+dp

容易想到贪心:吃饭慢的先打饭节约时间, 所以先将人按吃饭时间从大到小排序。

然后就是dp了: 首先,应该想到f[i][j][k]:前i个人,在1号窗口打饭总时间j,在2号窗口打饭总时间k

当然,这样会爆空间,所以想到去掉一维。

f[i][j]表示前i个人,在1号窗口打饭总时间j,最早吃完饭的时间

我们可以发现 j+k=前i个人打饭总和,k = sum(i)-j。 所以可以维护一个前缀和。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define maxn 200+10
 6 #define INF 2147483647
 7 #define rep(i,s,e) for(register int i=s;i<=e;++i)
 8 #define dwn(i,s,e) for(register int i=s;i>=e;--i)
 9 using namespace std;
10 inline int read()
11 {
12     int x=0,f=1;
13     char c=getchar();
14     while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
15     while(c>='0'&&c<='9') {x=x*10+c-'0'; c=getchar();}
16     return f*x;
17 }
18 inline void write(int x)
19 {
20     if(x<0) {putchar('-'); x=-x;}
21     if(x>9) write(x/10);
22     putchar(x%10+'0');
23 }
24 int n;
25 int sum[maxn];
26 int dp[maxn][maxn*maxn];
27 struct node
28 {
29     int a,b;
30 }lunch[maxn];
31 bool cmp(node x,node y)
32 {
33     return x.b>y.b;
34 }
35 int main()
36 {
37     n=read();
38     rep(i,1,n) {lunch[i].a=read();lunch[i].b=read();}
39     sort(lunch+1,lunch+n+1,cmp);
40     rep(i,1,n) sum[i]=sum[i-1]+lunch[i].a;
41     memset(dp,127,sizeof(dp));
42     dp[0][0]=0;
43     rep(i,1,n)
44         rep(j,0,sum[i])
45         {
46             if(j>=lunch[i].a) dp[i][j]=min(dp[i][j],max(dp[i-1][j-lunch[i].a],j+lunch[i].b));
47             if(sum[i]-j>=lunch[i].a) dp[i][j]=min(dp[i][j],max(dp[i-1][j],sum[i]-j+lunch[i].b));
48         }
49     int ans=INF;
50     rep(i,0,sum[n]) ans=min(ans,dp[n][i]);
51     write(ans);
52     return 0;
53 }

请各位大佬斧正(反正我不认识斧正是什么意思)

原文地址:https://www.cnblogs.com/handsome-zyc/p/12023999.html