【题解】SDOI2009学校食堂

　　不知道有没有人跟我有一样的感觉……实际上很多的状压DP都不难，然而调到心碎……这题题面看起来很长，还有混合的‘位运算’来吓唬人（实际上就是异或而已）。但实际上只要仔细阅读，发现也是一道水水的裸题。

　　首先，题目当中给出的信息是：\(B_{i} <= 7\)。看到这一条，心中已有八分笃定：在这样的环境下，估计是状压。然后就开始考虑转移的方程：先从暴力的状态开始，我们要确定没有后效性的状态，则有两个维度应该是必须的。一维代表 \(i\)，即现在 \(1 -> i\) 之间的同学都已经打到饭了，以及 \(j\) 即上一名打饭的同学的口味值。最后的一维状压，压 \(\left (i + 1, i + 8 \right )\) 号同学的打饭状态，后面的就不用了，因为第 \(i + 1\) 个人目前还没有打到饭，他最大只能容忍第 \(i + 8\) 名同学先打。

　　可是出现了一个问题：\(j\)的范围过大。所以不能存值，只能存编号。考虑在第\(i + 1\) 个人还没有打饭的情况下，上一个打饭的人只能在范围 \(\left (i - 7, i + 8 \right )\) 中，我们存下这一个编号，并且规定一个标准：第 \(i\) 名同学的编号为 \(7\)。这样，所有可能的同学编号均在 \(\left (0, 15 \right )\) 的范围内。

　　感觉我的状压dp代码有毒……食用需谨慎呐￣へ￣

#include <bits/stdc++.h>

using namespace std;

#define maxn 1005

#define INF 9999999

int T, CNST;

int n, a[maxn], t[maxn];

int f[maxn][][];

int read()

{

    int x = , k = ;

    char c;

    c = getchar();

    while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * k;

}

void Init()

{

    for(int i = ; i <= n; i ++)

        for(int j = ; j <= ; j ++)

            for(int k = ; k < CNST; k ++)

                f[i][j][k] = INF;

}

void update(int &x, int y) { x = x < y ? x : y; }

int main()

{

    T = read(), CNST = ( << ) - ;

    while(T --)

    {

        n = read();

        Init();

        for(int i = ; i <= n; i ++) a[i] = read(), t[i] = read();

        f[][][] = ;

        for(int i = ; i < n; i ++)

            for(int k = ; k < CNST; k ++)

            {

                for(int j = ; j <= ; j ++)

                {

                    if(f[i][j][k] >= INF) continue;

                    int tmp = k, minn = INF;

                    for(int s = ; s <=  && (i + s + ) <= n; s ++)

                        if(!((tmp >> s) & )) minn = min(minn, s + t[i + s + ]);

                    if(minn == INF || k & ) minn = ;

                    for(int s = ; s <= minn; s ++)

                    {

                        if((k >> s) & ) continue;

                        if(i + s +  > n) break;

                        int q = i + j -  >=  ? a[i + j - ] : ;

                        if(!i && !k) q = a[i + s + ];

                        int ret = q ^ a[i + s + ];

                        if(s +  <= ) update(f[i][s + ][k | ( << s)], f[i][j][k] + ret);

                    }

                    int q = (i + j - ) >=  ? a[i + j - ] : ;

                    if(!i && !k) q = a[i + ];

                    update(f[i + ][][k >> ], f[i][j][k] + (q ^ a[i + ]));

                    if(j && (k & )) update(f[i + ][j - ][k >> ], f[i][j][k]);

                }

            }

        int ans = INF;

        for(int j = ; j <= ; j ++)

            for(int k = ; k < CNST; k ++)

                ans = min(ans, f[n][j][k]);

        printf("%d\n", ans);

    }

    return ;

}

巴特西

【题解】SDOI2009学校食堂

最新文章

热门文章