題目描述

小F 的學校在城市的一個偏僻角落，所有學生都只好在學校吃飯。學校有一個食堂，雖然簡陋，但食堂大廚總能做出讓同學們滿意的菜肴。當然，不同的人口味也不一定相同，但每個人的口味都可以用一個非負整數表示。 由于人手不夠，食堂每次只能為一個人做菜。做每道菜所需的時間是和前一道菜有關的，若前一道菜的對應的口味是a，這一道為b，則做這道菜所需的時間為（a or b）-（a and b），而做第一道菜是不需要計算時間的。其中，or 和and 表示整數逐位或運算及逐位與運算，C語言中對應的運算符為“|”和“&”。

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

雖然同學們能夠理解學校食堂的這種做法，不過每個同學還是有一定容忍度的。也就是說，隊伍中的第i 個同學，最多允許緊跟他身后的Bi 個人先拿到飯菜。一旦在此之后的任意同學比當前同學先拿到飯，當前同學將會十分憤怒。因此，食堂做菜還得照顧到同學們的情緒。 現在，小F 想知道在滿足所有人的容忍度這一前提下，自己的學校食堂做完這些菜最少需要多少時間。

輸入輸出格式

輸入格式：

第一行包含一個正整數C，表示測試點的數據組數。 每組數據的第一行包含一個正整數N，表示同學數。 每組數據的第二行起共N行，每行包含兩個用空格分隔的非負整數Ti和Bi，表示按隊伍順序從前往后的每個同學所需的菜的口味和這個同學的忍受度。 每組數據之間沒有多余空行。

輸出格式：

包含C行，每行一個整數，表示對應數據中食堂完成所有菜所需的最少時間。

輸入輸出樣例

輸入樣例#1：
2 5 5 2 4 1 12 0 3 3 2 2 2 5 0 4 0 輸出樣例#1：
16 1

說明

對于第一組數據：

同學1允許同學2或同學3在他之前拿到菜；同學2允許同學3在他之前拿到菜；同學3比較小氣，他必須比他后面的同學先拿菜……

一種最優的方案是按同學3、同學2、同學1、同學4、同學5做菜，每道菜所需的時間分別是0、8、1、6及1。

【數據規模和約定】

對于30%的數據，滿足1 ≤ N ≤ 20。

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

存在30%的數據，滿足0 ≤ Bi ≤ 1。

存在65%的數據，滿足0 ≤ Bi ≤ 5。

存在45%的數據，滿足0 ≤ Ti ≤ 130。

題解：

狀壓$DP$。

設$f[i][j][k]$表示第$1$個人到第$i?1$個人已經打完飯，第$i$個人以及后面$7$個人是否打飯的狀態為$j$，當前最后一個打飯的人的編號為$i+k$（$k$的范圍為$?8$到$7$，所以用數組存時要加上$8$），那么轉移為：

當$j&1$為真，就表示第$i$個人已經打完飯，$i$之后的$7$個人中，還沒打飯的人就再也不會插入到第$i$個人前面了。所以這時候可以轉移到$f[i+1][j>>1][k?1]$，即$f[i+1][j>>1][k?1]=min(f[i+1][j>>1][k?1],f[i][j][k])$，不需要累積時間（因為在$j&1$為真的情況下，$f[i][j][k]$和$f[i+1][j>>1][k?1]$的意義是一樣的）。

而為什么意義是一樣的呢？因為可以看出，最后一個打飯的人的編號為$(i+1)+(k?1)=i+k$，和$f[i][j][k]$表示的一樣。而第$i$個人也打完了飯，所以滿足「第$1$個人到第$i$個人已經打完飯」這個條件。而$j>>1$就是說$i$之后的第$1$個人就是$i+1$之后的第$0$個人（就是$i+1$本人），$i$之后的第$2$個人就是$i+1$之后的第$1$個人，$i$之后的第$3$個人就是$i+1$之后的第$2$個人，…。這樣就可以看出意義一樣了。

當$j&1$為假時，是沒辦法轉移到$f[i+1]$的（因為$i+1$之前的人還有$i$沒有打完飯）。但是這時候可以把$i$以及$i$之后的$7$個人中選出一個人打飯，也就是枚舉$h$從$0$到$7$，$f[i][j|(1<<h)][h]=min(f[i][j|(1<<h)][h],f[i][j][k]+time(i+k,i+h))$，其中$time(i,j)$表示如果上一個人編號為$i$，當前的人編號為$j$，那么做編號為$j$的人的菜需要的時間。當然，這個轉移需要考慮到忍耐度的問題。這樣，在$i$和$i$之后的$7$個人，不是每一個還未打飯的人都可以先打飯的。因為編號在他之前的所有未打飯的人的忍耐度必須能忍受這個人在他們之前打飯。所以，在這里用了一個變量$r$來統計了一下，表示到目前為止的未打飯的人的忍受范圍（注意，不是忍耐度，忍受范圍是指能忍受在其之前打飯的最大位置）的最小值，對于任何一個人，如果$i+h>r$，就表示他無法滿足編號在他之前的所有人的忍受范圍，就不要考慮這個人了。代碼實現如下：

#include<iostream> #include<algorithm> #define f(i,l,r) for(i=(l);i<=(r);i++) #define dp(i,S,k) dp[i][S][k+8] using namespace std; const int MAXN=1005,INF=100000000; int T,n,dp[MAXN][1<<9][17],t[MAXN],b[MAXN]; inline int cal(int x,int y) {if(x==0) return 0;return t[x]^t[y]; } int main() {ios::sync_with_stdio(false);int i,j,S,k;cin>>T;while(T--){cin>>n;f(i,1,n){cin>>t[i]>>b[i];}f(i,0,n+1){f(S,0,(1<<8)-1){f(k,-8,7){dp(i,S,k)=INF;}}}dp(1,0,-1)=0;f(i,1,n){f(S,0,(1<<8)-1){f(k,-8,7){if(dp(i,S,k)==INF) continue;if(S&1){dp(i+1,S>>1,k-1)=min(dp(i,S,k),dp(i+1,S>>1,k-1));}else{int range=INF;f(j,0,7){if((S&(1<<j))==0){if(i+j>range) break;range=min(range,i+j+b[i+j]);dp(i,S|(1<<j),j)=min(dp(i,S|(1<<j),j),dp(i,S,k)+cal(i+k,i+j));}}}}} }int ans=INF;f(i,-8,0){ans=min(ans,dp(n+1,0,i));}cout<<ans<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的[SDOI2009]学校食堂Dining 洛谷p2157的全部內容，希望文章能夠幫你解決所遇到的問題。

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