JZOJ 3643.拯救莫莉斯

观察数据范围,发现 nm50nm \le 50 这个条件有蹊跷。
根据 mnm \le n 可得 m50m \le \sqrt{50}m7m \le 7
于是考虑状压。

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

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

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

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

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

代码:

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

arknights