观察数据范围，发现 \(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
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);
}