題目描述

小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

分析

這題我真沒想出來（我好菜啊
一開始想的是用 $f[i][s_1][s_2][k]$ 表示到了第 $i$ 人，$i$ 前面 $7$ 位狀態為 $s_1$，后面 $8$ 位（包括 $i$ ) 狀態是 $s_2$ ，最后一個打飯的是 $k$ 的最小時間。
這樣設計的原因主要是 $i$ 前面的人可以還沒打飯，后面的人可以已經打了飯。
但是這樣狀態是很冗余的，有很多不合法狀態，復雜度也要升天。
（于是在這種情況下我很羞恥地看了題解
仔細想想，我們擔心的部分是 $i$ 前面有還沒打飯的，我們將最前面沒打飯的記作 $p$。那么 $1$ 到 $p?1$ 都是打了飯的，而 $p+7$后面必然是沒打飯的。這樣子對于這種狀態，我們為之開那么多的空間，實在是不值啊！！！
我們用 $f[i][s][k]$ 表示前 $i?1$ 人已經打了飯，$i$ 及后面 $7$ 人狀態為 $s$，最后一個打飯的離 $i$ 的距離為 $k$ 的最小時間。這樣子我們上面提及的狀態肯定是能被覆蓋的，即是 $f[p][s][k]$。
接下來我們看轉移方程吧。
首先如果 $s$ 最后一位是 $1$，即代表 $i$ 已經打過飯了。
那么 $f[i+1][s>>1][k?1]=f[i][s][k]$
然后如果 $i$ 沒有打過飯，我們就枚舉接下來打飯的那個，記離 $i$ 的距離為 $j$，顯然 $0\le j\le 7$。
$f[i][s|(1<<j)][j]=f[i][s][k]+val(i+j,i?k)$
然后如果我們枚舉到的 $k$ 超過前面某一個未打飯人的容忍度，就要break掉了。
具體細節看代碼吧。

代碼如下

//f[i + 1][sta >> 1][k - 1] = min(f[i][sta][k]) //f[i][sta | (1 << j)][i + j] = min(f[i][sta][k] + val) #include <bits/stdc++.h> #define inf 2e9 using namespace std; int f[1005][1 << 8][16], t[1005], b[1005]; int main(){int i, j, k, sta, val, n, m, T, minn, ans;scanf("%d", &T);while(T--){ans = inf;scanf("%d", &n);memset(f, 120, sizeof(f));for(i = 1; i <= n; i++) scanf("%d%d", &t[i], &b[i]);f[1][0][7] = 0;for(i = 1; i <= n; i++){for(sta = 0; sta < (1 << 8); sta++){for(k = -8; k <= 7; k++){if(f[i][sta][k + 8] > inf) continue;if(sta & 1) f[i + 1][sta >> 1][k + 7] = min(f[i + 1][sta >> 1][k + 7], f[i][sta][k + 8]);else{minn = inf;for(j = 0; j <= 7; j++){if(1 << j & sta) continue;if(i + j > minn) break;minn = min(minn, i + j + b[i + j]);if(i + k >= 1) val = t[i + k] ^ t[i + j];else val = 0;f[i][sta | (1 << j)][j + 8] = min(f[i][sta | (1 << j)][j + 8], f[i][sta][k + 8] + val);}}}}}for(i = 0; i <= 8; i++) ans = min(ans, f[n + 1][0][i]);printf("%d\n", ans);}return 0; }

總結

以上是生活随笔為你收集整理的SDOI 2009 学校食堂（好难的状压QAQ的全部內容，希望文章能夠幫你解決所遇到的問題。

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