这题难度不算小，2007山东省选题。

难度：省选/NOI-

题目描述

        小F 的学校在城市的一个偏僻角落，所有学生都只好在学校吃饭。学校有一个食堂，虽然简陋，但食堂大厨总能做出让同学们满意的菜肴。当然，不同的人口味也不一定相同，但每个人的口味都可以用一个非负整数表示。 由于人手不够，食堂每次只能为一个人做菜。做每道菜所需的时间是和前一道菜有关的，若前一道菜的对应的口味是a，这一道为b，则做这道菜所需的时间为（a or b）-（a and b），而做第一道菜是不需要计算时间的。其中，or 和and 表示整数逐位或运算及逐位与运算，C语言中对应的运算符为“|”和“&”。

        学生数目相对于这个学校还是比较多的，吃饭做菜往往就会花去不少时间。因此，学校食堂偶尔会不按照大家的排队顺序做菜，以缩短总的进餐时间。
        虽然同学们能够理解学校食堂的这种做法，不过每个同学还是有一定容忍度的。也就是说，队伍中的第i 个同学，最多允许紧跟他身后的Bi 个人先拿到饭菜。一旦在此之后的任意同学比当前同学先拿到饭，当前同学将会十分愤怒。因此，食堂做菜还得照顾到同学们的情绪。 现在，小F 想知道在满足所有人的容忍度这一前提下，自己的学校食堂做完这些菜最少需要多少时间。

输入输出格式

输入格式：

        第一行包含一个正整数C，表示测试点的数据组数。 每组数据的第一行包含一个正整数N，表示同学数。 每组数据的第二行起共N行，每行包含两个用空格分隔的非负整数Ti和Bi，表示按队伍顺序从前往后的每个同学所需的菜的口味和这个同学的忍受度。 每组数据之间没有多余空行。

输出格式：

        包含C行，每行一个整数，表示对应数据中食堂完成所有菜所需的最少时间。

输入输出样例

Sample input

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

Sample output

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。
        令dp(r,k,p)表示从第r（从0开始）个人开始，上一个人打饭的人距离r位置为k，且r后面七个人（含自己）的打饭状态为p（状态压缩，0表示未打饭、1表示已经打饭），那么可知状态转移方程：

        p&1为1表示r这个人已经打好饭了，这时的dp值直接就是dp(r+1,k-1,p>>1)。p>>1表示将r的数据剔除。
        p&1为0表示r这个人没有打饭，这时枚举他和他后面没有打饭的人来进行转移。last是可以枚举的最大值，如果过了这一值，便会有人愤怒。期初的last=min(B[r],n-r-1)，但是在枚举过程中需要不断更新last，以防止有其他人愤怒。
        转移细节：k的取值范围一定为[-8,7]，这个容易从转移方程上得出。p的取值范围即为[0,(1<<8)-1]（注意不要越界即可）。可以开循环来求这个三维表，由方程可得r和p都应该降序枚举。答案即为min{dp(0,l,1<<l)},0≤l≤last（last理解同上）。
        从本题中吸取的一个教训是循环一定要将可能的状态都涉及到。一开始我就将p的取值范围用B[r]处理，使得一些状态被忽略导致WA。也就是说，用循环来DP时，一定要保证所有可能的状态都被涉及到（可以有理论上不存在的状态，但应尽量将它们剔除），答案才能正确。求解时可能会求出一些不存在的状态的值，它们不影响正确结果的求解，只是会降低程序效率，应适当剔除这些状态。但是注意不要因此将一些正确的状态也盲目剔除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<cstdio>

#define N 1000+1
#define S(x) x+9
using namespace std;
int dp[N][20][1 << 8], T[N], B[N], n;

int read() {
    char e = static_cast<char>(getchar());
    while (e < '0' || e > '9')e = static_cast<char>(getchar());
    int s = 0;
    while (e >= '0' && e <= '9')s = s * 10 + e - '0', e = static_cast<char>(getchar());
    return s;
}

int main() {
    int c = read();
    for (int ci = 0; ci < c; ci++) {
        n = read();
        for (int i = 0; i < n; i++)T[i] = read(), B[i] = read();//口味，忍耐程度
        for (int i = n - 1; i >= 0; i--) {//人的序号
            for (int p = (1 << min(8, n - i)) - 1; p >= 0; p--) {//后续状压情况
                for (int k = max(-8, -i); k <= min(B[i], n - i - 1); k++) {//上一个的相对位置
                    if ((p & 1) != 0) {
                        if (i != n - 1)dp[i][S(k)][p] = dp[i + 1][S(k - 1)][p >> 1];//自己已吃，直接转移
                        else dp[i][S(k)][p] = 0;
                    } else {
                        int last = min(B[i], n - i - 1), ans = 0x7fffffff;
                        for (int l = 0; l <= last; l++) {
                            if ((p & (1 << l)) != 0)continue;
                            last = min(last, l + B[i + l]);
                            ans = min(ans, dp[i][S(l)][p | (1 << l)] + (T[i + k] | T[i + l]) - (T[i + k] & T[i + l]));
                        }
                        dp[i][S(k)][p] = ans;
                    }
                }
            }
        }
        int ans = 0x7fffffff, last = min(B[0], n - 1);
        for (int i = 0; i <= last; i++)last = min(last, i + B[i]), ans = min(ans, dp[0][S(i)][1 << i]);
        cout << ans << endl;
    }
    return 0;
}