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

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

Output
包含C行，每行一個整數(shù)，表示對應(yīng)數(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ù)：同學(xué)1允許同學(xué)2或同學(xué)3在他之前拿到菜；同學(xué)2允許同學(xué)3在他之前拿到菜；同學(xué)3比較小氣，他必須比他后面的同學(xué)先拿菜…… 一種最優(yōu)的方案是按同學(xué)3、同學(xué)2、同學(xué)1、同學(xué)4、同學(xué)5做菜，每道菜所需的時間分別是0、8、1、6及1。

對于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。

---

這題思維難度有點小大，我們設(shè)f[i][sta][k]代表當(dāng)前考慮到第i個人，第i個人和他之后7人是否吃飯的狀態(tài)為sta，最后一個吃飯的和i的相對位置為k。轉(zhuǎn)移分為兩種：

• sta&1==1：\(f[i][sta][k]\Longrightarrow f[i+1][sta>>1][k-1]\)
• 枚舉i及之后7人的吃飯狀態(tài)：\(f[i][sta][k]+get(i+k,i+l)\Longrightarrow f[i][sta|(1<<l)][l]\)，稍微注意一下l枚舉的最大范圍，而且k可能可以大于B[i]，因為i可能已經(jīng)吃完飯了

/*program from Wolfycz*/ #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define inf 0x7f7f7f7f #define f(x,y,z) dp[x][y][z+8] using namespace std; typedef long long ll; typedef unsigned int ui; typedef unsigned long long ull; inline int read(){int x=0,f=1;char ch=getchar();for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';return x*f; } inline void print(int x){if (x>=10) print(x/10);putchar(x%10+'0'); } const int N=1e3; int v[N+10],w[N+10];//wait int dp[N+10][(1<<8)+10][20]; int get(int x,int y){return !x?0:v[x]^v[y];} int main(){for (int T=read();T;T--){int n=read();for (int i=1;i<=n;i++) v[i]=read(),w[i]=read();for (int i=1;i<=n+1;i++)for (int sta=0;sta<1<<8;sta++)for (int k=-8;k<=7;k++)f(i,sta,k)=inf;f(1,0,-1)=0;for (int i=1;i<=n;i++){for (int sta=0;sta<1<<8;sta++){for (int k=-8;k<=7;k++){if (f(i,sta,k)<inf){if (sta&1) f(i+1,sta>>1,k-1)=min(f(i+1,sta>>1,k-1),f(i,sta,k));else{for (int l=0,r=inf;l<8;l++){if (!(sta&(1<<l))){if (i+l>r) break;r=min(r,i+l+w[i+l]);f(i,sta|(1<<l),l)=min(f(i,sta|(1<<l),l),f(i,sta,k)+get(i+k,i+l));}}}}}}}int Ans=inf;for (int k=-8;k<0;k++) Ans=min(Ans,f(n+1,0,k));printf("%d\n",Ans);}return 0; }

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

總結(jié)

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

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