洛谷 2577 [ZJOI2005] 午餐

同样是一道dp好题，我死也想不出dp方程，看了题解才知道

还是我太蒻了

看看题目描述吧

我们设dp方程dp[i][j]，表示前i个人，在1队打饭的总时间为j，吃完饭要花的最小时间

这题有一个小小的贪心，就是要让打饭吃饭慢的人先打饭，这样显然可以保证最优

于是考虑一下转移

dp[i][j]=min(dp[i][j],max(dp[i-1][j-d[i].a],j+d[i].b),max(dp[i-1][j],sum[i]-j+d[i].b));

sum[i]是一个前缀和，记录了前i个人打饭的总时间

解释一下max(dp[i-1][j-d[i].a],j+d[i].b）和 max(dp[i-1][j],sum[i]-j+d[i].b)

前者dp[i-1][j-d[i].a]表示当前人打饭的时间对总共的吃饭时间无影响，j+d[i].b表示当前人吃饭的时间对总时间有影响

后者同理

代码很短

 1 #include <cstdlib>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <iostream>
 5 #include <cstring>
 6 using namespace std;
 7 const int N=205;
 8 struct node
 9 {
10     int a,b;
11 }d[N];
12 int sum[N],n,dp[N][N*N];
13 bool cmp(node a,node b)
14 {
15     return a.b>b.b;
16 }
17 int main()
18 {
19     scanf("%d",&n);
20     for(int i=1;i<=n;i++)
21     {
22         scanf("%d %d",&d[i].a,&d[i].b);
23     }
24     sort(d+1,d+n+1,cmp);
25     for(int i=1;i<=n;i++)
26         sum[i]=sum[i-1]+d[i].a;
27     memset(dp,0x3f,sizeof(dp));
28     dp[0][0]=0;
29     for(int i=1;i<=n;i++)
30         for(int j=1;j<=sum[i];j++)
31         {
32             if(j-d[i].a>=0)
33                 dp[i][j]=min(dp[i][j],max(dp[i-1][j-d[i].a],j+d[i].b));
34             dp[i][j]=min(dp[i][j],max(dp[i-1][j],sum[i]-j+d[i].b));
35         }
36     int ans=99999999;
37     for(int i=0;i<=sum[n];i++)
38     {
39         ans=min(ans,dp[n][i]);
40     }
41     printf("%d
",ans);
42     return 0;
43 }