描述

上午的訓(xùn)練結(jié)束了，THU ACM小組集體去吃午餐，他們一行N人來到了著名的十食堂。這里有兩個打飯的窗口，每個窗口同一時刻只能給一個人打飯。由于每個人的口味（以及胃口）不同，所以他們要吃的菜各有不同，打飯所要花費的時間是因人而異的。另外每個人吃飯的速度也不盡相同，所以吃飯花費的時間也是可能有所不同的。

THU ACM小組的吃飯計劃是這樣的：先把所有的人分成兩隊，并安排好每隊中各人的排列順序，然后一號隊伍到一號窗口去排隊打飯，二號隊伍到二號窗口去排隊打飯。每個人打完飯后立刻開始吃，所有人都吃完飯后立刻集合去六教地下室進行下午的訓(xùn)練。

現(xiàn)在給定了每個人的打飯時間和吃飯時間，要求安排一種最佳的分隊和排隊方案使得所有人都吃完飯的時間盡量早。

假設(shè)THU ACM小組在時刻0到達十食堂，而且食堂里面沒有其他吃飯的同學(xué)（只有打飯的師傅）。每個人必須而且只能被分在一個隊伍里。兩個窗口是并行操作互不影響的，而且每個人打飯的時間是和窗口無關(guān)的，打完飯之后立刻就開始吃飯，中間沒有延遲。

現(xiàn)在給定N個人各自的打飯時間和吃飯時間，要求輸出最佳方案下所有人吃完飯的時刻。

輸入

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

輸出

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

樣例輸入[復(fù)制]

5
2 2
7 7
1 3
6 4
8 5

樣例輸出[復(fù)制]

17

提示

所有輸入數(shù)據(jù)均為不超過200的正整數(shù)。

樣例說明 方案如下： 窗口1： 窗口2： 7 7 1 3 6 4 8 5 2 2

標(biāo)簽

ZJOI2005 這道題其實一看我們知道要結(jié)合貪心，這個道理其實是跟烹調(diào)方案是一樣的 烹調(diào)方案告訴我們貪心應(yīng)該從兩個相鄰的元素來入手 那么這道題里面有一個條件是吃飯時間長的人應(yīng)該先排在前面 證明：假設(shè)有兩個人吃飯時間是ai,bi,aj,bj其中bi>bj 如果是i先打飯的話，最長的時間就是ai+aj+bj 反之就是ai+aj+bi 顯然進行比較的話會發(fā)現(xiàn)前者更優(yōu)，得證。進行排序 想看dp方程的直接翻到第二種猜想下面吧，接下來一點內(nèi)容講我自己總結(jié)出來的一點點思路 然后就是一個dp過程 我們找出題目中的幾個狀態(tài)：12號窗口人數(shù)，12號當(dāng)前所需排隊+吃飯的最大值（好像沒有別的了） 那么設(shè)狀態(tài)就有這么一個問題，首先很顯然f[i]一個狀態(tài)是啥也刻畫不了的 在不考慮空間大小的時候在刻畫兩個隊伍的時候肯定是要考慮各自的時間的，顯然用f[i][j][k]來刻畫。 那么這里就引入一個問題：到底狀態(tài)是記錄人數(shù)，還是最大的排隊時間數(shù)+吃飯數(shù)，還是記錄排隊到當(dāng)前的排隊時間數(shù)（非吃飯）。結(jié)果又該記錄什么東西？ 首先我們來考慮一下如果我們設(shè)人數(shù)為狀態(tài)的話，那么有一維是多余的，壓縮成兩維f[i][j]代表i個人第一個窗口排j個人， 那么就有一個問題，因為只能存儲一個值就會發(fā)現(xiàn)記錄第一個會丟失第二個窗口的時間，你會發(fā)現(xiàn)無法刻畫最大值和每一個窗口現(xiàn)在的狀態(tài) 第一種猜想pass 考慮我們按第二種方式構(gòu)建dp，顯然? f[i][j][k]? ?刻畫前? ?i? ?個人，第一個窗口最大當(dāng)前排隊吃飯最大時間是? ? j? ? ，第二個是? ? k? ? ?，然后往下轉(zhuǎn)移就是當(dāng)前人到第一個或者是第二個窗口然后更新。 但我們忽略了這個狀態(tài)到底存儲什么值的問題，因為題目要求的值已經(jīng)是維度了，而且如果你存當(dāng)前的排隊時間貌似沒有dp的大小轉(zhuǎn)移的性質(zhì)了，就成雞肋了 第二種猜想pass 那么我們只能考慮最后一種，很顯然還是f[i][j][k]，?刻畫前? ?i? ?個人，第一個窗口當(dāng)前排隊時間是? ? j? ? ，第二個是? ? k? ? ?，然后我們這個dp存什么值？顯然就是最大的排隊+吃飯的時間 這樣做有什么好處？吃飯的時間維度里面進行了描述，轉(zhuǎn)移到下一個人加上他自己的時間就可以了，這樣就可以進行狀態(tài)轉(zhuǎn)移了 考慮第i個人的轉(zhuǎn)移，顯然是到第一個窗口或者第二個窗口，dp方程就出來了 dp[i][j][k]=min(dp[i][j][k],max(dp[i-1][j-e[i].a][k],j+e[i].b)); //這是第一個窗口 dp[i][j][k]=min(dp[i][j][k],max(dp[i-1][j][k-e[i].a],k+e[i].b)); //第二個

為什么我們要max，因為我們記錄最大值，這個人排在這里可能比原來要長，取min不說了

但這個時候我們看一下會發(fā)現(xiàn)空間爆炸了怎么辦？？？？？？？借鑒我之前的dp經(jīng)驗肯定是要壓一波空間了

滾動數(shù)組+1，如果你滾掉第一維理論上可以，但是 j , k 都是4e4級別的，舍掉

只能滾掉 j 或者 k ，假設(shè)滾掉第二個窗口 k ,接著就會發(fā)現(xiàn)那個k+e[i].b怎么辦？？？？

仔細看下其實發(fā)現(xiàn) j + k 是前 i 個人排隊時間的前綴和，高高興興滾掉

然后為什么可以正序，因為i由i-1滾過來，不會重疊

over！

總結(jié)：一道貪心+dp的好題目，貪心我竟然想偏了。。。。唉，還是太菜了QAQ dp說實話應(yīng)該與貪心隔離開來思考，這樣就不會是一團糟了，很多題的維度就是狀態(tài)，有時候還是前綴甚者是后綴，逐個嘗試分析吧 太菜了555 code： 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #define N 1004 6 using namespace std; 7 struct node{ 8 int a,b; 9 }e[N]; 10 bool cmp(node a,node b){ 11 return a.b>b.b; 12 } 13 int sum[N]; 14 int f[205][40005]; 15 int main(){ 16 int n; 17 cin>>n; 18 for(int i=1;i<=n;i++) 19 cin>>e[i].a>>e[i].b; 20 sort(e+1,e+n+1,cmp); 21 for(int i=1;i<=n;i++) 22 sum[i]=sum[i-1]+e[i].a; 23 memset(f,0x3f3f3f3f,sizeof f); 24 f[0][0]=0; 25 for(int i=1;i<=n;i++){ 26 for(int j=0;j<=sum[i];j++){ 27 if(j>=e[i].a)f[i][j]=min(f[i][j],max(f[i-1][j-e[i].a],j+e[i].b)); 28 f[i][j]=min(f[i][j],max(f[i-1][j],sum[i]-j+e[i].b)); 29 } 30 } 31 int ans=2147483647; 32 for(int i=0;i<=sum[n];i++) 33 ans=min(ans,f[n][i]); 34 cout<<ans; 35 return 0; 36 }

額，還要補前面的題解，慢慢來

轉(zhuǎn)載于:https://www.cnblogs.com/saionjisekai/p/9683596.html

總結(jié)

以上是生活随笔為你收集整理的ZJOI2005午餐的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。