Description

小F的學校在城市的一個偏僻角落，所有學生都只好在學校吃飯。學校有一個食堂，雖然簡陋，但食堂大廚總能做出讓同學們滿意的菜肴。當然，不同的人口味也不一定相同，但每個人的口味都可以用一個非負整數(shù)表示。?
由于人手不夠，食堂每次只能為一個人做菜。做每道菜所需的時間是和前一道菜有關(guān)的，若前一道菜的對應的口味是a，這一道為b，則做這道菜所需的時間為（a or b）-（a and b），而做第一道菜是不需要計算時間的。其中，or和and表示整數(shù)逐位或運算及逐位與運算，C語言中對應的運算符為”｜”和”＆”。?
學生數(shù)目相對于這個學校還是比較多的，吃飯做菜往往就會花去不少時間。因此，學校食堂偶爾會不按照大家的排隊順序做菜，以縮短總的進餐時間。?
雖然同學們能夠理解學校食堂的這種做法，不過每個同學還是有一定容忍度的。也就是說，隊伍中的第i個同學，最多允許緊跟他身后的Bi個人先拿到飯菜。一旦在此之后的任意同學比當前同學先拿到飯，當前同學將會十分憤怒。因此，食堂做菜還得照顧到同學們的情緒。?
現(xiàn)在，小F想知道在滿足所有人的容忍度這一前提下，自己的學校食堂做完所有菜最少需要多少時間。

Input

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

Output

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

Sample Input

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

Sample Output

16?
1

Hint

數(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。

題解： 這題狀態(tài)定義的很詭,明確i只跟i-b[i] 和 i+b[i] 一段能扯上關(guān)系，所以我們就處理這一段 定義F[i][j][k] i為當前的菜的位置，j為前一個的位置與i的差(abs<=7)，k為i到i+b[i] 這一段的狀態(tài) 值得注意的是枚舉順序 k要寫在j前面 .... k滿足遞增順序，j可以無序的 1 #include <algorithm> 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 using namespace std; 8 const int N=1005; 9 int t[N],b[N],f[N][19][(1<<8)+5],INF; 10 int pd(int i,int j){ 11 if(!i)return i; 12 return (t[i]|t[j])-(t[i]&t[j]); 13 } 14 void work(){ 15 int n,lim,to,mov=8; 16 scanf("%d",&n); 17 memset(f,127/3,sizeof(f));INF=f[0][0][0]; 18 for(int i=1;i<=n;i++)scanf("%d%d",&t[i],&b[i]); 19 f[1][-1+mov][0]=0; 20 for(int i=1;i<=n;i++){ 21 for(int k=0,tmp=(1<<8)-1;k<=tmp;k++){ 22 for(int j=-7;j<=7;j++){ 23 if(f[i][j+mov][k]==INF)continue; 24 if(k&1)f[i+1][j-1+mov][k>>1]=min(f[i+1][j-1+mov][k>>1],f[i][j+mov][k]); 25 lim=INF; 26 for(int g=0;g<=7;g++){ 27 if((1<<g)&k)continue; 28 if(i+g>lim)break; 29 lim=min(lim,i+g+b[i+g]); 30 to=(k|(1<<g)); 31 f[i][g+mov][to]=min(f[i][g+mov][to],f[i][j+mov][k]+pd(i+j,i+g)); 32 } 33 } 34 } 35 } 36 int ans=INF; 37 for(int i=1;i<=15;i++)ans=min(ans,f[n][i][1]); 38 printf("%d\n",ans); 39 } 40 int main() 41 { 42 freopen("dining.in","r",stdin); 43 freopen("dining.out","w",stdout); 44 int T; 45 scanf("%d",&T); 46 while(T--) 47 work(); 48 return 0; 49 }

?

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

總結(jié)

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

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