洛谷 3886 「JLOI2009」神秘的生物

发表于 | 分类于 |

插头 DP 模板题之一。
考虑将轮廓线上的连通块运用最小表示法编号来表示状态，容易发现轮廓线上至多有 \(5\) 个连通块，使用 \(8\) 进制压缩即可。

转移时考虑三种情况：

  1. 该格子不扩展。此时需要判断上插头所在连通块是否因此闭合。
  2. 该格子形成新连通块。前提是没有上插头和左插头。
  3. 该格子与上插头和左插头所在连通块合并。

以及注意要更新最小表示法。

代码参考了 @GNAQ。

代码： 

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
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define bits(x) (((x) - 1) * 3)
using namespace std;
const int N = 9;
const int MX = 1e6;
const int hash_mod = 70921;
int n,a[N + 5][N + 5];
int f[2][MX + 5],ans = -0x3f3f3f3f;
int key[2][MX + 5],tot[2],first[2][hash_mod + 5],pre[2][MX + 5];
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];
}
inline int update(int s,int v)
{
    int vis[N + 5],cnt = 0,ret = 0;
    memset(vis,0,sizeof vis);
    for(register int i = 1;i <= n;++i)
        if((s >> bits(i)) & 7)
            ret += (vis[(s >> bits(i)) & 7] ? vis[(s >> bits(i)) & 7] : (vis[(s >> bits(i)) & 7] = ++cnt)) << bits(i);
    cnt == 1 && (ans = max(ans,v));
    return ret;
}
int main()
{
    scanf("%d",&n);
    for(register int i = 1;i <= n;++i)
        for(register int j = 1;j <= n;++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 <= n;++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)) & 7,left = (s >> bits(j - 1)) & 7;
                int v = f[cur][k];
                s -= (up << bits(j));
                for(register int l = 1;l <= n;++l)
                    if(up == ((s >> bits(l)) & 7))
                    {
                        trans(cur ^ 1,update(s,v),v);
                        break;
                    }
                v += a[i][j],s = key[cur][k];
                if(!up && !left)
                    s += 7 << bits(j);
                else
                {
                    s -= up << bits(j),s += max(up,left) << bits(j);
                    if(up && left)
                        for(register int l = 1;l <= n;++l)
                            if(((s >> bits(l)) & 7) == min(up,left))
                                s += abs(up - left) << bits(l);
                }
                trans(cur ^ 1,update(s,v),v);
            }
        }
    printf("%d\n",ans);
}