JZOJ 3643 「GDOI2014」拯救莫莉斯

发表于 | 分类于 |

观察数据范围，发现 \(nm \le 50\) 这个条件有蹊跷。
根据 \(m \le n\) 可得 \(m \le \sqrt{50}\) 即 \(m \le 7\)。
于是考虑状压。

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

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

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

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

可以预处理 \(cost_{i,j}\) 表示第 \(i\) 行状态为 \(j\) 的花费。

代码： 

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
#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);
}

Gitalking ...