麻麻我会写插头dp了！
推荐陈丹琦论文：https://wenku.baidu.com/view/3e90d32b453610661ed9f4bd.html
破题调一年
#include <cstdio>
#include <cstring> const int N=<<;
int n,m,tt,a1=0xcfcfcfcf,st[],a[][],b[N],g[N][],f[][][N];
void up(int &x,int y) {if(x<y) x=y;}
void dfs(int x,int s,int k) {
if(x==m+) {
if(!k) {
for(int i=,tp=;i<m;i++) {
int t=(s>>(i*))&;
if(t==) st[++tp]=i;
else if(t==) g[s][i]=st[tp],g[s][st[tp]]=i,tp--;
}
b[++tt]=s;
} return;
}
dfs(x+,s<<,k),dfs(x+,s<<|,k+);
if(k) dfs(x+,s<<|,k-);
} int main() {
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) for(int j=;j<=m;j++) scanf("%d",&a[i][j]);
memset(f,0xcf,sizeof f),f[][][]=,f[][][(<<(m*))|(*(<<(m-)*))]=a[][],dfs(,,);
for(int i=;i<=n;i++) {
for(int j=;j<m;j++) {
for(int k=;k<=tt;k++) if(f[i][j][b[k]]!=0xcfcfcfcf) {
int t1=(b[k]>>((m-j)*))&,t2=(b[k]>>((m-j-)*))&,t3=<<((m-j)*),t4=<<((m-j-)*);
int s=b[k]&((<<((m+)*))--t3*-t4*),t=f[i][j][b[k]]+a[i][j+];
if(!t1&&!t2) up(f[i][j+][s],t-a[i][j+]),up(f[i][j+][s|t3|(t4*)],t);
else if(!t1) up(f[i][j+][s|(t3*t2)],t),up(f[i][j+][s|(t4*t2)],t);
else if(!t2) up(f[i][j+][s|(t3*t1)],t),up(f[i][j+][s|(t4*t1)],t);
else if(t1==&&t2==) up(f[i][j+][s-(<<(g[b[k]][m-j-]*))],t);
else if(t1==&&t2==) {
if(b[k]==t3+t4*&&a1<t) a1=t;
} else if(t1==&&t2==) up(f[i][j+][s],t);
else up(f[i][j+][s+(<<(g[b[k]][m-j]*))],t);
}
}
for(int k=;k<=tt;k++) if(f[i][m][b[k]]!=0xcfcfcfcf) {
int t1=(b[k]>>(m*))&,t3=<<(m*),t4=<<((m-)*),s=(b[k]&((<<(m*))-))>>,t=f[i][m][b[k]]+a[i+][];
if(!t1) up(f[i+][][s],t-a[i+][]),up(f[i+][][s|t3|(t4*)],t);
else up(f[i+][][s|(t3*t1)],t),up(f[i+][][s|(t4*t1)],t);
}
}
printf("%d",a1);
return ;
}