【BZOJ1899】[Zjoi2004]Lunch 午餐

Description

上午的訓練結束了，THU ACM小組集體去吃午餐，他們一行N人來到了著名的十食堂。這里有兩個打飯的窗口，每個窗口同一時刻只能給一個人打飯。由于每個人的口味（以及胃口）不同，所以他們要吃的菜各有不同，打飯所要花費的時間是因人而異的。另外每個人吃飯的速度也不盡相同，所以吃飯花費的時間也是可能有所不同的。 THU ACM小組的吃飯計劃是這樣的：先把所有的人分成兩隊，并安排好每隊中各人的排列順序，然后一號隊伍到一號窗口去排隊打飯，二號隊伍到二號窗口去排隊打飯。每個人打完飯后立刻開始吃，所有人都吃完飯后立刻集合去六教地下室進行下午的訓練。 現在給定了每個人的打飯時間和吃飯時間，要求安排一種最佳的分隊和排隊方案使得所有人都吃完飯的時間盡量早。 假設THU ACM小組在時刻0到達十食堂，而且食堂里面沒有其他吃飯的同學（只有打飯的師傅）。每個人必須而且只能被分在一個隊伍里。兩個窗口是并行操作互不影響的，而且每個人打飯的時間是和窗口無關的，打完飯之后立刻就開始吃飯，中間沒有延遲。 現在給定N個人各自的打飯時間和吃飯時間，要求輸出最佳方案下所有人吃完飯的時刻。

Input

第一行一個整數N，代表總共有N個人。 以下N行，每行兩個整數 Ai，Bi。依次代表第i個人的打飯時間和吃飯時間。

Output

一個整數T，代表所有人吃完飯的最早時刻。

Sample Input

5
2 2
7 7
1 3
6 4
8 5

Sample Output

17

HINT

方案如下：

窗口1： 窗口2：
7 7 1 3
6 4 8 5
2 2

【限制】
所有輸入數據均為不超過200的正整數。

題解：首先自己討論一下就能知道，如果只有一個隊列，那么一定是讓吃飯時間慢的先打飯。那么如果有兩個隊列，那么其中的每一個都一定是按吃飯時間遞減的，所以我們先將所有人按吃飯時間排序。

然后設f[i][j][k]表示前i個人，A隊列總等待時間為j，B隊列總等待時間為k，所需要的最小總時間。下一步比較神，用sum[i]表示前i個人等待時間的前綴和，則j+k=sum[i]，所以我們可以優化掉一維。

然后就容易DP了。

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct node {int a,b; }p[210]; int n,m,sum,ans; int f[2][40010]; inline int rd() {int ret=0,f=1; char gc=getchar();while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();return ret*f; } bool cmp(node a,node b) {return a.b>b.b; } int main() {n=rd();int i,j,d;for(i=1;i<=n;i++) p[i].a=rd(),p[i].b=rd();sort(p+1,p+n+1,cmp);memset(f,0x3f,sizeof(f));f[0][0]=0;for(i=1;i<=n;i++){d=i&1,memset(f[d],0x3f,sizeof(int)*(sum+1)),sum+=p[i].a;for(j=0;j<=sum;j++){f[d][j]=max(f[d^1][j],sum-j+p[i].b);if(j>=p[i].a) f[d][j]=min(f[d][j],max(f[d^1][j-p[i].a],j+p[i].b));}}ans=1<<30;for(i=0;i<=sum;i++) ans=min(ans,f[n&1][i]);printf("%d",ans);return 0; }

?

轉載于:https://www.cnblogs.com/CQzhangyu/p/7468822.html

總結

以上是生活随笔為你收集整理的【BZOJ1899】[Zjoi2004]Lunch 午餐 贪心+DP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。