P1546學校食堂

描述

小F的學校在城市的一個偏僻角落，所有學生都只好在學校吃飯。學校有一個食堂，雖然簡陋，但食堂大廚總能做出讓同學們滿意的菜肴。當然，不同的人口味也不一定相同，但每個人的口味都可以用一個非負整數(shù)表示。

由于人手不夠，食堂每次只能為一個人做菜。做每道菜所需的時間是和前一道菜有關(guān)的，若前一道菜的對應的口味是a，這一道為b，則做這道菜所需的時間為（a or b）-（a and b），而做第一道菜是不需要計算時間的。其中，or和and表示整數(shù)逐位或運算及逐位與運算，C語言中對應的運算符為”｜”和”＆”。

學生數(shù)目相對于這個學校還是比較多的，吃飯做菜往往就會花去不少時間。因此，學校食堂偶爾會不按照大家的排隊順序做菜，以縮短總的進餐時間。

雖然同學們能夠理解學校食堂的這種做法，不過每個同學還是有一定容忍度的。也就是說，隊伍中的第i個同學，最多允許緊跟他身后的Bi個人先拿到飯菜。一旦在此之后的任意同學比當前同學先拿到飯，當前同學將會十分憤怒。因此，食堂做菜還得照顧到同學們的情緒。

現(xiàn)在，小F想知道在滿足所有人的容忍度這一前提下，自己的學校食堂做完所有菜最少需要多少時間。

格式

輸入格式

輸入文件dining.in的第一行包含一個正整數(shù)C，表示測試點的數(shù)據(jù)組數(shù)。

每組數(shù)據(jù)的第一行包含一個正整數(shù)N，表示同學數(shù)。

每組數(shù)據(jù)的第二行起共N行，每行包含兩個用空格分隔的非負整數(shù)Ti和Bi，表示按隊伍順序從前往后的每個同學所需的菜的口味和這個同學的忍受度。

每組數(shù)據(jù)之間沒有多余空行。

輸出格式

輸出文件dining.out包含C行，每行一個整數(shù)，表示對應數(shù)據(jù)中食堂完成所有菜所需的最少時間。

樣例1

樣例輸入1

2 5 5 2 4 1 12 0 3 3 2 2 2 5 0 4 0

樣例輸出1

16 1

限制

各個測試點1s

提示

【樣例說明】
對于第一組數(shù)據(jù)：
同學1允許同學2或同學3在他之前拿到菜；同學2允許同學3在他之前拿到菜；同學3比較小氣，他必須比他后面的同學先拿菜……
一種最優(yōu)的方案是按同學3、同學2、同學1、同學4、同學5做菜，每道菜所需的時間分別是0、8、1、6及1。

【數(shù)據(jù)規(guī)模和約定】
對于30%的數(shù)據(jù)，滿足1 ≤ N ≤ 20。

對于100%的數(shù)據(jù)，滿足1 ≤ N ≤ 1,000，0 ≤ Ti ≤ 1,000，0 ≤ Bi ≤ 7，1 ≤ C ≤ 5。

存在30%的數(shù)據(jù)，滿足0 ≤ Bi ≤ 1。

存在65%的數(shù)據(jù)，滿足0 ≤ Bi ≤ 5。

存在45%的數(shù)據(jù)，滿足0 ≤ Ti ≤ 130。

觀察b數(shù)組的大小范圍就不難想到動規(guī)，但是實際上沒有一個好的狀態(tài)是很難過這道題的

經(jīng)過分析我們知道:

假如第i個人還沒有打飯，則i+7絕不可能打過飯了，因為第i個人的最大容忍度不會超過7；

如果第i個人之前全部取完了，則目前為止最后一個打飯的人不可能是i-8之前的人，因為i-1不可能先于i-9及之前的人打飯。

第i個人最多與后面7個人產(chǎn)生關(guān)系，所以可以用一個集合S來記錄i和i后面7個人中已經(jīng)打過飯的人

所以設計狀態(tài)：
f [i][S][k]表示前i-1個人都打過飯了，i和i之后的7個人的已打飯者的集合S，上一個打飯的人與i的相對位置是k(可能為負)，在這種情況下的最優(yōu)代價。

因此這里我們就有兩種情況需要討論

1.如果第i個人沒有打飯,那么狀態(tài)f(i,s,k)就可以轉(zhuǎn)化為:f(i+1,s>>1,k-1),相當于將整體往右平移一個單位

2.如果第i個人已經(jīng)打了飯,那么第i個人就可以直接轉(zhuǎn)化到i+1~i+7的任意一個人j，前提是j號同學沒有打飯

即f(i,s|(1<<q),q)=min(f(i,s|(1<<q),q),f(i,s,k)+Cost(i+k,i+q))

具體細節(jié)看代碼

#include<cstdio> #include<iostream> #define f(xx,yy,zz) (g[xx][yy][zz+8]) using namespace std; const int maxn=1005,inf=1e9; inline void _read(int &x){char t=getchar();bool sign=true;while(t<'0'||t>'9'){if(t=='-')sign=false;t=getchar();}for(x=0;t>='0'&&t<='9';t=getchar())x=x*10+t-'0';if(!sign)x=-x; } int n,c,b[maxn],t[maxn],all,g[maxn][300][20]; int Cost(int x,int y){return x==0?0:t[x]^t[y];} int main(){_read(c);all=(1<<8)-1;while(c--){_read(n);int i,j,k,q,ans=inf;for(i=1;i<=n;i++){_read(t[i]);_read(b[i]);}for(i=1;i<=n+1;i++)for(j=0;j<=all;j++)for(k=-8;k<8;k++)f(i,j,k)=inf;f(1,0,-1)=0;for(i=1;i<=n;i++)for(j=0;j<=all;j++)for(k=-8;k<8;k++)if(f(i,j,k)<inf)if(j&1)f(i+1,j>>1,k-1)=min(f(i+1,j>>1,k-1),f(i,j,k));else {int lim=inf;//lim相當于向右延伸的最大限制，更新i+1~i+7號人中能忍受的最小值for(q=0;q<=7;q++)if(!(j&(1<<q))){if(i+q>lim)break;lim=min(lim,i+q+b[i+q]);f(i,j|(1<<q),q)=min(f(i,j|(1<<q),q),f(i,j,k)+Cost(i+k,i+q));}}for(i=-8;i<8;i++)ans=min(ans,f(n+1,0,i));printf("%d\n",ans);} }

總結(jié)

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

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