洛谷 3190.「HNOI2007」神奇游乐园

也是个板题(

使用括号表示法压缩轮廓线上的插头状态。
转移时讨论上插头和左插头的存在情况即可。

代码:

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <cstdio>
#include <cstring>
#include <algorithm>
#define bits(x) ((x) - 1 << 1)
using namespace std;
const int N = 100;
const int M = 6;
const int MX = 1e6;
const int hash_mod = 70921;
int n,m,a[N + 5][M + 5];
int f[2][MX + 5],ans = -0x3f3f3f3f;
int key[2][MX + 5],tot[2],pre[2][MX + 5],first[2][hash_mod + 5];
inline void trans(int cur,int s,int v)
{
int h = s % hash_mod;
for(register int i = first[cur][h];i;i = pre[cur][i])
if(key[cur][i] == s)
{
f[cur][i] = max(f[cur][i],v);
return ;
}
key[cur][++tot[cur]] = s,f[cur][tot[cur]] = v,pre[cur][tot[cur]] = first[cur][h],first[cur][h] = tot[cur];
}
int main()
{
scanf("%d%d",&n,&m);
for(register int i = 1;i <= n;++i)
for(register int j = 1;j <= m;++j)
scanf("%d",a[i] + j);
trans(0,0,0);
for(register int i = 1,cur = 0;i <= n;++i)
{
for(register int j = 1;j <= tot[cur];++j)
key[cur][j] <<= 2;
for(register int j = 1;j <= m;++j,cur ^= 1)
{
memset(first[cur ^ 1],0,sizeof first[cur ^ 1]),tot[cur ^ 1] = 0;
for(register int k = 1;k <= tot[cur];++k)
{
int s = key[cur][k],up = (s >> bits(j + 1)) & 3,left = (s >> bits(j)) & 3;
int v = f[cur][k];
if(!up && !left)
trans(cur ^ 1,s,v);
v += a[i][j];
if(!up && !left)
i < n && j < m && (trans(cur ^ 1,s + (1 << bits(j)) + (2 << bits(j + 1)),v),1);
else if(!up && left)
i < n && (trans(cur ^ 1,s,v),1),
j < m && (trans(cur ^ 1,s - (left << bits(j)) + (left << bits(j + 1)),v),1);
else if(up && !left)
j < m && (trans(cur ^ 1,s,v),1),
i < n && (trans(cur ^ 1,s - (up << bits(j + 1)) + (up << bits(j)),v),1);
else if(up == 1 && left == 1)
for(register int l = j + 1,cnt = 0;l <= m + 1;++l)
{
((s >> bits(l)) & 3) == 1 && ++cnt,
((s >> bits(l)) & 3) == 2 && --cnt;
if(!cnt)
{
trans(cur ^ 1,s - (1 << bits(j)) - (1 << bits(j + 1)) - (1 << bits(l)),v);
break;
}
}
else if(up == 2 && left == 2)
for(register int l = j,cnt = 0;l;--l)
{
((s >> bits(l)) & 3) == 2 && ++cnt,
((s >> bits(l)) & 3) == 1 && --cnt;
if(!cnt)
{
trans(cur ^ 1,s - (2 << bits(j)) - (2 << bits(j + 1)) + (1 << bits(l)),v);
break;
}
}
else if(up == 1 && left == 2)
trans(cur ^ 1,s - (1 << bits(j + 1)) - (2 << bits(j)),v);
else
s == (1 << bits(j)) + (2 << bits(j + 1)) && (ans = max(ans,v));
}
}
}
printf("%d\n",ans);
}