「Bzoj 1226」「SDOI2009」学校食堂 (状压DP)

发表于 | 分类于 | | + s

BZOJ 1226
题意：见上。

看见$B_i \leq 7$就要留意状压了。(本蒟蒻没想到)
这题一个状态和前和后都有关，这样状压DP就排上用场。前面DP顺推，后面的状态状压记录。
然后可以设$dp(i,st)$为$[1,i-1]$吃完饭了，$[i, i+7]$是否吃饭的状态
发现这样无法转移，不能算出做菜时间，那么加一维$k$表示上一层吃饭的人相对$i$的位置的距离$k \in [{\color{red}{-8}}, 7]$
注意要到$-8$，因为可以后面$7$个人都吃完再轮到$i$吃。
转移考虑$i$是否吃了。
1、吃了的话，则
$$
dp(i+1,st / 2, k-1)=\min(dp(i,st,k))
$$
其中$st / 2$意义为左移，$k-1$的原因是之前吃的位置相对$i+1$是远了。
这两个式子表示的意义实际是一样。
2、没吃，就枚举$h\in [0,7]$吃
$$
dp(i, st | h, h)=\min(dp(i, st, k) + T(i+k,i+h))
$$
其中$T(x,y)=x \operatorname{xor} y$，即题目中的$x\operatorname{or} y - x \operatorname{and} y$

还要考虑容忍度。因为每个人的$B_i$不同，所以边扫描边维护最小的容忍区间，即代码中的bd

因为这题又刷表又递推，$i$要循环到$n$，注意集合的最大值为1<<8

1、一个状态和前和后都有关，这样状压DP就排上用场。前面DP顺推，后面的状态状压记录
2、边界是否+1想好。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<stack>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

int T;

namespace flyinthesky {

    const int MAXN = 1000 + 5;

    int n, C[MAXN], B[MAXN];
    int dp[MAXN][300][21]; 

    void clean() {
        for (int i = 0; i <= n; ++i) 
        for (int j = 0; j <= 289; ++j)
        for (int k = 0; k <= 20; ++k) dp[i][j][k] = 1000000000;
    }
    int solve() {

        scanf("%d", &n);
        clean();
        for (int i = 1; i <= n; ++i) scanf("%d%d", &C[i], &B[i]);

        dp[1][0][-1 + 8] = 0;

        for (int i = 1; i <= n; ++i) {
            for (int st = 0; st <= (1 << 8) - 1; ++st) {
                for (int k = -8; k <= 7; ++k) {
                    if (!(i + k >= 0 && i + k <= n)) continue ;
                    if (st & 1) 
                        dp[i + 1][st >> 1][k - 1 + 8] = dp[i][st][k + 8];
                    else {
                        int bd = 1000000000; 
                        for (int h = 0; h <= 7; ++h) if (!(st & (1 << h))) {
                            if (i + h > bd) break ;
                            bd = min(bd, i + h + B[i + h]);
                            dp[i][st | (1 << h)][h + 8] = min(dp[i][st | (1 << h)][h + 8], dp[i][st][k + 8] + ((i + k == 0) ? 0 : ( (C[i + k]) ^ (C[i + h]) )) );
                        }
                    }
                }
            }
        }

        int ans = 1000000000;
        for (int k = -8; k <= 7; ++k) ans = min(ans, dp[n][1][k + 8]);

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

        return 0;
    }
}
int main() {
    scanf("%d", &T);
    while (T--) flyinthesky::solve();
    return 0;
}
------ 本文结束 ------