JZOJ 3643 「GDOI2014」拯救莫莉斯

观察数据范围，发现 nm≤50 这个条件有蹊跷。
根据 m≤n 可得 m≤√50 即 m≤7。
于是考虑状压。

发现这个题跟其他题有点区别。
转移要同时考虑上下两行。

考虑设 fi,j,k 表示转移到前 i−1 行的状态都合法，第 i 行的状态为 j，第 i−1 行的状态为 k 的最小价值。
那么转移就比较显然了。
枚举行数、最近三行的状态，考虑三行中间那行是否合法并转移。

还有一点需要注意，答案的状态为 fn+1,0,x 而非 fn,x,y。
因为根据定义，后者只考虑了 n−1 行的状态。

然鹅题目还要求最小的油库个数，简单地再开一个 g 数组在转移的同时更新即可。

可以预处理 costi,j 表示第 i 行状态为 j 的花费。

代码：

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 50;
const int M = 7;
int n,m,full,ans1 = 0x3f3f3f3f,ans2;
int a[N + 5][M + 5];
int cost[N + 5][(1 << M) + 5];
int f[N + 5][(1 << M) + 5][(1 << M) + 5],g[N + 5][(1 << M) + 5][(1 << M) + 5];
int main()
{
    memset(f,0x3f,sizeof f);
    scanf("%d%d",&n,&m);
    full = (1 << m) - 1;
    for(register int i = 1;i <= n;++i)
    {
        for(register int j = 1;j <= m;++j)
            scanf("%d",a[i] + j);
        for(register int j = 0;j <= full;++j)
            for(register int k = 1;k <= m;++k)
                if(j & (1 << k - 1))
                    cost[i][j] += a[i][k];
    }
    for(register int i = 0;i <= full;++i)
        f[1][i][0] = cost[1][i],g[1][i][0] = __builtin_popcount(i);
    for(register int i = 2;i <= n + 1;++i)
        for(register int j = 0;j <= full;++j)
            for(register int k = 0;k <= full;++k)
                for(register int l = 0;l <= full;++l)
                    if(((j | l | k | (k << 1) | (k >> 1)) & full) == full)
                    {
                        if(f[i - 1][k][l] + cost[i][j] < f[i][j][k])
                            f[i][j][k] = f[i - 1][k][l] + cost[i][j],g[i][j][k] = g[i - 1][k][l] + __builtin_popcount(j);
                        else if(f[i - 1][k][l] + cost[i][j] == f[i][j][k] && g[i - 1][k][l] + __builtin_popcount(j) < g[i][j][k])
                            g[i][j][k] = g[i - 1][k][l] + __builtin_popcount(j);
                    }
    for(register int i = 0;i <= full;++i)
        if(f[n + 1][0][i] < ans1)
            ans1 = f[n + 1][0][i],ans2 = g[n + 1][0][i];
        else if(f[n + 1][0][i] == ans1 && g[n + 1][0][i] < ans2)
            ans2 = g[n + 1][0][i];
    printf("%d %d\n",ans2,ans1);
}