大致题意： 有一张棋盘，每个格子有一个权值（可能为负）。一只蚂蚁从任意一个格点出发向上走，按两次右转、两次左转的顺序转弯（每次转弯前可以走任意长度），并在最后一次转弯（一定是右转）时右转三次。已知：蚂蚁不会在一个位置转多次；除起点外蚂蚁不会重复经过任一格点，且蚂蚁最终会回到起点。给出蚂蚁左转的次数/2的值，求蚂蚁所经过路线围成封闭图形的最大值。
前言
这是少数我能自己做出来的(DP)题。。。
我能做出来的(DP)题=(DP)水题。
大致思路
题面很复杂，但稍微画画图分析一下，就会发现蚂蚁围成的图形必然是一条水平线之上高-低-高-低-...-高的一个图形。说起来有点抽象，但实际上就是长这个样子：（好像画得也挺抽象。。。）
因此，我们可以枚举行数(i)，然后设(f_{j,p,x})表示(DP)到第(j)列，顶端在第(p)行，转弯状态为(x)时的方案数（(x=0,2,...,2k)表示右转，(1,3,...,2k-1)表示左转）。
设(f_{j,p,x})表示(DP)到第(j)列，顶端在第(p)行，转弯状态为(x)时的方案数（(x=0,2,...,2k)表示右转，(1,3,...,2k-1)表示左转）。
设(t=sum_{w=p}^ia_{w,j})（可以在(DP)同时维护），则有两种方式转移：
- 从前一列到这一列没有转弯，则(f_{j,p,x}=f_{j-1,p,x}+t)。
- 前一个是没转弯，这一个当然是转弯了啊。。。但转弯又分两种：
- 高度增加（(x)为偶数）：(f_{j,p,x}=max_{w=p+1}^if_{j-1,w,x-1}+t)。
- 高度降低（(x)为奇数）：(f_{j,p,x}=max_{w=1}^{p-1}f_{j-1,w,x-1}+t)。
其中(max)的值我们可以事先预处理前缀(max)和后缀(max)。
注意一些细节，例如第一列无法从前一列转移，可以单独处理。
然后，对于每一列都要考虑(x=0)的特殊情况，因为此时我们可以以该列作为起始列，即初始化(f_{j,p,0}=t)。
具体实现详见代码。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100
#define K 10
#define Gmax(x,y) (x<(y)&&(x=(y)))
using namespace std;
int n,m,k,a[N+5][N+5],f[N+5][N+5][2*K+5],g[N+5][N+5][2*K+5],h[N+5][N+5][2*N+5];
int main()
{
RI i,j,p,x,t;scanf("%d%d%d",&n,&m,&k);
for(i=1;i<=n;++i) for(j=1;j<=m;++j) scanf("%d",&a[i][j]);
RI ans=-1e9;for(i=1;i<=n;++i)
{
for(t=0,p=i;p;--p) for(f[1][p][0]=(t+=a[p][1]),//初始化第一列
x=1;x<=2*k;++x) f[1][p][x]=g[1][p][x]=h[1][p][x]=-1e9;
for(g[1][i][0]=f[1][i][0],p=i-1;p;--p) g[1][p][0]=max(g[1][p+1][0],f[1][p][0]);
for(h[1][1][0]=f[1][1][0],p=2;p<=i;++p) h[1][p][0]=max(h[1][p-1][0],f[1][p][0]);
for(j=2;j<=m;++j)//处理之后的每一列
{
for(t=0,p=i;p;--p)//枚举顶端所在行
{
for(x=0;x<=2*k;++x) f[j][p][x]=g[j][p][x]=h[j][p][x]=-1e9;//清空
for(f[j][p][0]=(t+=a[p][j]),x=0;x<=2*k;++x)//维护t，注意特殊处理x=0
Gmax(f[j][p][x],f[j-1][p][x]+t),//直接转移
x&&!(x&1)&&p^i&&Gmax(f[j][p][x],g[j-1][p+1][x-1]+t),//高度增加
x&1&&p^1&&Gmax(f[j][p][x],h[j-1][p-1][x-1]+t);//高度降低
}
for(x=0;x<=2*k;++x) for(g[j][i][x]=f[j][i][x],
p=i-1;p;--p) g[j][p][x]=max(g[j][p+1][x],f[j][p][x]);
for(x=0;x<=2*k;++x) for(h[j][1][x]=f[j][1][x],
p=2;p<=i;++p) h[j][p][x]=max(h[j][p-1][x],f[j][p][x]);
}
for(j=1;j<=m;++j) for(p=i;p;--p) Gmax(ans,f[j][p][2*k]);//统计答案
}return printf("%d",ans),0;
}