洛谷P2577 午餐【贪心】【线性dp】

题目：https://www.luogu.org/problemnew/show/P2577

题意：n个人每个人有一个打饭时间和吃饭时间，将他们分成两个队伍。每个人打到饭之后就马上去吃饭。问怎么安排可以让总体的吃饭时间最短。

思路：首先贪心还是很好想的。某个队伍的总吃饭时间实际上是打饭结束+吃饭时间最晚的那个时间。

一个队伍前面的那些人，如果他们吃完饭的时间都不超过总的排队时间的话，根本不需要考虑他们。而队伍的排队时间如果安排好了，是固定的。跟安排的顺序没有关系。

所以我们应该要把吃饭时间长的往前放。因为排队时间不受顺序影响但是吃饭时间受顺序的影响。

然后我们可以考虑怎么给他们分成两队。

首先可以考虑$dp[i][j][k]$表示考虑到第$i$个人，第一条队伍排队时间是$j$第二条队伍排队时间是$k$的时候，最早全部吃完饭的时间。

但是我们发现$j$和$k$存在关系，因为两个队伍总的排队时间是固定的。所以我们可以用$sum[i]$来维护排队时间的前缀和。就可以减少一个维度了。

所以我们可以用$dp[i][j]$表示考虑到第$i$个人，第一条队伍排队时间是$j$最早全部吃完饭的时间。此时显然第二条队伍的排队时间是$sum[i] - j$

于是有$dp[i][j] = min(max(dp[i-1][j-get[i]], j + eat[i]), max(dp[i - 1][j], sum[i] - j + eat[i]))$分别表示第$i$个人排在第一个队伍和排在第二个队伍。

 #include<cstdio>

 #include<cstdlib>

 #include<map>

 #include<set>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #include<cmath>

 #include<stack>

 #include<queue>

 #include<iostream>

 #define inf 0x3f3f3f3f

 using namespace std;

 typedef long long LL;

 typedef pair<int, int> pr;

 int n;

 const int maxn = ;

 struct node{

     int get, eat;

 }stu[maxn];

 int sum[maxn];

 int dp[maxn][maxn * maxn * ];

 bool cmp(node a, node b)

 {

     return a.eat > b.eat;

 }

 int main()

 {

     scanf("%d", &n);

     memset(dp, 0x3f, sizeof(dp));

     for(int i = ; i <= n; i++){

         scanf("%d%d", &stu[i].get, &stu[i].eat);

     }

     sort(stu + , stu +  + n, cmp);

     for(int i = ; i <= n; i++){

         sum[i] = sum[i - ] + stu[i].get;

     }

     dp[][] = ;

     for(int i = ; i <= n; i++){

         for(int j = ; j <= sum[i]; j++){

             if(j >= stu[i].get)dp[i][j] = min(dp[i][j], max(dp[i - ][j - stu[i].get], j + stu[i].eat));

             dp[i][j] = min(dp[i][j], max(dp[i - ][j], sum[i] - j + stu[i].eat));

         }

     }

     int ans = inf;

     for(int j = ; j <= sum[n]; j++){

         ans = min(ans, dp[n][j]);

     }

     printf("%d\n", ans);

     return ;

 }

巴特西

洛谷P2577 午餐【贪心】【线性dp】

最新文章

热门文章