神奇游乐园问题

解题思路：

本题要求的是一个回路，而且是一个权值和最大的回路。求所有路径的方案可以用状态压缩 $dp$，而本题是一个棋盘上的问题，因此可以发现这是一个棋盘上的连通性状态压缩 $dp$ 问题，那么就可以想到用插头 $dp$。

本题的列数较小，行数较大，因此我们可以横着以每一行作为分界线来做。以每次分界线上出来的边的情况作为状态。

设 $f_{i,j,S}$ 表示枚举到 $(i,j)$ 时，分界线的状态是 $S$ 的所有回路的权值最大值。

由于本题求的是回路，因此对于分界线上出来的边一定是两两配对的，并且回路之间不存在相交，因此如果将每条路径的左端点作为左括号，右端点作为右括号，那么分界线的状态就是一定是一个括号序列，因此我们可以用括号表示法来维护分界线的状态，$1$ 表示左括号，$2$ 表示右括号，$0$ 表示没有边出来。这样每个状态就都是一个三进制的数，我们再将它填成四进制，用位运算来优化操作。

接下来分析插头 $dp$ 的状态转移，需要分成多种情况来考虑。

设当前枚举到的格子为 $(i,j)$，它左边这条边的状态为 $x$，上面这条边的状态为 $y$，下面这条边的状态为 $z$，右边这条边的状态为 $w$。则当前格子递推完之后分界线上的 $x,y$ 将变成 $z,w$。设 $g(i,j)$ 表示 $(i,j)$ 的权值

第一种情况：$x,y$ 都为 $0$，则 $(i,j)$ 就有用和不用两种情况，如果不用 $(i,j)$，则状态不变，权值不变；如果用 $(i,j)$，由于 $x,y$ 没有边出来，因此此时只有可能是 $z,w$ 都有边出来，此时新状态应该是将 $z,w$ 变成 $1,2$，$z,w$ 就是原本 $x,y$ 的位置，此时权值和应该加上 $g(i,j)$

第二种情况：$x$ 为 $0$，$y$ 不为 $0$，则 $y$ 有一条边出来，这条边可以往 $z,w$ 两个方向走，因此分别枚举往两个方向走，对应的更新一下状态，权值和同样加上 $g(i,j)$

第三种情况：$x$ 不为 $0$，$y$ 为 $0$，则 $x$ 有一条边出来，这条边可以往 $z,w$ 两个方向走，因此分别枚举往两个方向走，对应的更新一下状态，权值和同样加上 $g(i,j)$

第四种情况：$x,y$ 都为 $1$，此时 $x,y$ 都有边出来，且 $x,y$ 所在路径的右边分别有一个右端点，此时 $x,y$ 出现的边都到达 $(i,j)$，显然这两条边应该连上，此时 $x,y$ 所在的路径合并，那么我们就要将右边两个右端点中靠左的一个右端点变成左端点。权值和加上 $g(i,j)$

第五种情况：$x,y$ 都为 $2$，此时 $x,y$ 都有边出来，且 $x,y$ 所在路径的左边分别有一个左端点，此时 $x,y$ 出现的边都到达 $(i,j)$，显然这两条边应该连上，此时 $x,y$ 所在的路径合并，那么我们就要将左边两个左端点中靠右的一个左端点变成右端点。权值和加上 $g(i,j)$

第六种情况：$x$ 为 $2$，$y$ 为 $1$，此时 $x,y$ 都有边出来，$x$ 所在的路径左边有一个左端点，$y$ 所在的路径的右边有一个右端点，此时 $x,y$ 出现的边都到达 $(i,j)$，显然这两条边应该连上，此时左边的点恰好就是左端点，右边的点恰好就是右端点，此时其他点的状态不需要改变。权值和加上 $g(i,j)$

第七种情况：$x$ 为 $1$，$y$ 为 $2$，此时 $x,y$ 都有边出来，$x$ 所在的路径右边有一个右端点，$y$ 所在路径左边有一个左端点，但是由于图中不存在两条香蕉的路径，因此 $x$ 和 $y$ 此时一定属于同一条路径，此时 $x,y$ 出现的边都到达 $(i,j)$，显然这两条边应该连上，如果此时分界线上没有其他的边出来了，那么此时就形成回路了，此时的回路权值和要记得加上 $g(i,j)$，由于本题不用连上所有格子，因此任何位置都可以形成回路，此时我们用当前回路更新一下答案。

以上就是插头 $dp$ 的状态转移，后面几种情况由于 $x,y$ 都有边，所以 $z,w$ 一定都没有边，所以记得将 $x,y$ 位置上的状态改为 $0$。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 130, M = 301;

int n, m;
int g[N][N]; //地图
int q[2][N]; //每次滚动的有效状态在哈希表中的编号
int cnt[2]; //每次滚动的有效状态数量
int h[2][M]; //滚动哈希表
int v[2][M]; //滚动哈希表中每个状态的权值

int find(int cur, int x) //在哈希表中查找 x 所在的位置
{
    int t = x % M;
    while(h[cur][t] != -1 && h[cur][t] != x)
        if(++t == M)
            t = 0;
    return t;
}

void insert(int cur, int state, int w) //将 state 插入当前滚动的哈希表中
{
    int t = find(cur, state);
    if(h[cur][t] == -1)
    {
        h[cur][t] = state, v[cur][t] = w;
        q[cur][++cnt[cur]] = t;
    }
    else v[cur][t] = max(v[cur][t], w);
}

int get(int state, int k) //返回 state 四进制表示下第 k 位数
{
    return state >> k * 2 & 3;
}

int set(int k, int v) //构造一个四进制表示下第 k 位是 v 的数
{
    return v * (1 << k * 2);
}

int main()
{
    scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &g[i][j]);

    int res = -1e8;
    memset(h, -1, sizeof h); //初始化哈希表
    int cur = 0;
    insert(cur, 0, 0); //最开始的状态都是 0，权值也是 0

    //插头 dp
    for(int i = 1; i <= n; i++)
    {
        //将行尾状态转化成行首状态
        for(int j = 1; j <= cnt[cur]; j++)
            h[cur][q[cur][j]] <<= 2;

        for(int j = 1; j <= m; j++)
        {
            int last = cur;
            //初始化
            cur ^= 1, cnt[cur] = 0;
            memset(h[cur], -1, sizeof h[cur]);

            for(int k = 1; k <= cnt[last]; k++) //枚举所有有效状态进行转移
            {
                int state = h[last][q[last][k]], w = v[last][q[last][k]];
                int x = get(state, j - 1), y = get(state, j);
                if(!x && !y) //情况 1
                {
                    insert(cur, state, w);
                    if(i < n && j < m)
                        insert(cur, state + set(j - 1, 1) + set(j, 2), w + g[i][j]);
                }
                else if(x && !y) //情况 2
                {
                    if(j < m) insert(cur, state - set(j - 1, x) + set(j, x), w + g[i][j]);
                    if(i < n) insert(cur, state, w + g[i][j]);
                }
                else if(!x && y) //情况 3
                {
                    if(j < m) insert(cur, state, w + g[i][j]);
                    if(i < n) insert(cur, state + set(j - 1, y) - set(j, y), w + g[i][j]);
                }
                else if(x == 1 && y == 1) //情况 4
                {
                    //将靠左的右端点改成左端点
                    for(int u = j + 1, s = 1; ; u++)
                    {
                        int z = get(state, u);
                        if(z == 1) s++;
                        else if(z == 2)
                        {
                            if(--s == 0)
                            {
                                insert(cur, state - set(j - 1, x) - set(j, y) - set(u, 1), w + g[i][j]);
                                break;
                            }
                        }
                    }
                }
                else if(x == 2 && y == 2) //情况 5
                {
                    //将靠右的左端点改成右端点
                    for(int u = j - 2, s = 1; ; u--)
                    {
                        int z = get(state, u);
                        if(z == 2) s++;
                        else if(z == 1)
                        {
                            if(--s == 0)
                            {
                                insert(cur, state - set(j - 1, x) - set(j, y) + set(u, 1), w + g[i][j]);
                                break;
                            }
                        }
                    }
                }
                else if(x == 2 && y == 1) //情况 6
                {
                    insert(cur, state - set(j - 1, x) - set(j, y), w + g[i][j]);
                }
                else if(x == 1 && y == 2 && state - set(j - 1, x) - set(j, y) == 0) //情况 7
                {
                    res = max(res, w + g[i][j]); //更新答案
                }
            }
        }
    }
    printf("%d\n", res);

    return 0;
}