/*
经典问题，f[x][i][j][k]表示第x步三个人分别在第i行，第j行，第k行时所能达到最大值，
i,j,k顺推逆推皆可，因为用到的是f[x-1][][][]；
初值为f[1][1][1][1]=a[1][1]；
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <cstdlib>
using namespace std;

int f[41][21][21][21];
int n;
int a[22][22];

int max1(int a,int b,int c,int d,int f,int g,int h,int i)
{
    int ans;
    ans=max(a,b);
    ans=max(ans,c);
    ans=max(ans,d);
    ans=max(ans,f);
    ans=max(ans,h);
    ans=max(ans,i);
    ans=max(ans,g);
    return ans;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    f[1][1][1][1]=a[1][1];
    for(int x=1;x<=2*n-1;x++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                for(int k=1;k<=n;k++)
                {
                    int i1=x-i+1;int j1=x-j+1;int k1=x-k+1;
                    if(i1<0||j1<0||k1<0)    continue;
                    f[x][i][j][k]=max1(f[x-1][i-1][j][k],f[x-1][i][j-1][k],
                                      f[x-1][i][j][k-1],f[x-1][i-1][j-1][k],
                                      f[x-1][i-1][j][k-1],f[x-1][i][j-1][k-1],
                                      f[x-1][i-1][j-1][k-1],f[x-1][i][j][k])+a[i][i1]+a[j][j1]+a[k][k1];//最后一个状态别忘了x也要-1
                    if(i==j)
                        f[x][i][j][k]-=a[i][i1];
                    if(j==k)
                        f[x][i][j][k]-=a[j][j1];
                    if(i==k)
                        f[x][i][j][k]-=a[i][i1];
                    if(i==k&&k==j)
                        f[x][i][j][k]+=a[i][i1];
                }
    cout<<f[2*n-1][n][n][n]<<endl;
    return 0;
}
     

/*
算是比较普通的dp写法吧，把六维降到四维写。
*/
#include <iostream>
#include <cmath>
using namespace std;
int mp[21][21],N,dp[41][21][21][21];
int main()
{
cin>>N;
int y1,y2,y3;
for(int y=1;y<=N;y++)
for(int x=1;x<=N;x++)
cin>>mp[x][y];
for(int s=1;s<=N+N-1;s++)
for(int x1=1;x1<=s&&x1<=N;x1++)
for(int x2=1;x2<=s&&x2<=N;x2++)
for(int x3=1;x3<=s&&x3<=N;x3++)
{
y1=s-x1+1;y2=s-x2+1;y3=s-x3+1;//转换
if(y1>N||y2>N||y3>N)continue;
dp[s][x1][x2][x3]=max(
max(max(dp[s-1][x1][x2][x3],dp[s-1][x1-1][x2][x3]),
max(dp[s-1][x1-1][x2][x3-1],dp[s-1][x1-1][x2-1][x3])),
max(max(dp[s-1][x1][x2][x3-1],dp[s-1][x1-1][x2-1][x3-1]),
max(dp[s-1][x1][x2-1][x3],dp[s-1][x1][x2-1][x3-1])))
+mp[x1][y1];//8个状态判断
if(x1!=x2||y1!=y2)dp[s][x1][x2][x3]+=mp[x2][y2];//判断2与1的重叠
if((x1!=x3||y1!=y3)&&(x2!=x3||y2!=y3))dp[s][x1][x2][x3]+=mp[x3][y3];//判断3的重叠
}
cout<<dp[N+N-1][N][N][N]<<endl;
return 0;
}

#include <stack>
#include <queue>
#include <string>
#include <cmath>
#include <vector>
#include <cctype>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;
int a[25][25]={0},f[45][45][45][45]={0};

int main()
{  //代码看着比较难受，大家凑合着看吧
    ios :: sync_with_stdio(false);
    int n,m,t;
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    m=2*n-2;
    f[0][1][1][1]=a[1][1];//赋边界值，不要忘了
    for(int s=1;s<=m;s++)//三条线路共同开始，循环步数
        for(int i=1;i<=n;i++)//第1条
            for(int j=1;j<=n;j++)//第2条
                for(int k=1;k<=n;k++)//第3条
                {
                    if(i==j&&j==k)//三条线路重合的情况，一一列举
                        t=a[i][s+2-i];//知道了行就能知道列，公式:步数+2-行数，大家可以试验一下
                    else if(i==j)
                        t=a[i][s+2-i]+a[k][s+2-k];
                    else if(i==k)
                        t=a[i][s+2-i]+a[j][s+2-j];
                    else if(j==k)//两个点重合的情况
                        t=a[j][s+2-j]+a[i][s+2-i];
                    else //不重合的情况
                        t=a[i][s+2-i]+a[j][s+2-j]+a[k][s+2-k];
                    f[s][i][j][k]=max(f[s-1][i][j][k],max(f[s-1][i][j-1][k-1],max(f[s-1][i-1][j][k-1],max(f[s-1][i-1][j-1][k],max(f[s-1][i-1][j][k],max(f[s-1][i][j-1][k],max(f[s-1][i][j][k-1],f[s-1][i-1][j-1][k-1])))))))+t;
                }//到达三个点有八种方案，max（求当前最优解）
    cout<<f[m][n][n][n]<<endl;
    return 0;
}

6维数组水过

#include<bits/stdc++.h>
using namespace std;
int tot=0;
short int a[21][21];
short int dp[22][22][22][22][22][22];
int GETMAX(int b1,int b2,int c1,int c2,int d1,int d2,int e1,int e2)
{
int m,p;
int l=max(b1,b2);
int t=max(c1,c2);
if (t>l) m=t;
else m=l;
l=max(d1,d2);
t=max(e1,e2);
if (t>l) p=t;
else p=l;
return max(p,m);
}
int main()
{
int n,k;
cin>>n;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for (int i1=1;i1<=n;i1++)
for (int j1=1;j1<=n;j1++)
for (int i2=1;i2<=n;i2++)
for (int j2=1;j2<=n;j2++)
for (int i3=1;i3<=n;i3++)
for (int j3=1;j3<=n;j3++)
{
dp[1][1][1][1][1][1]=a[1][1];
dp[i1][j1][i2][j2][i3][j3]=GETMAX(dp[i1-1][j1][i2-1][j2][i3-1][j3],dp[i1-1][j1][i2-1][j2][i3][j3-1],dp[i1-1][j1][i2][j2-1][i3-1][j3],dp[i1-1][j1][i2][j2-1][i3][j3-1],dp[i1][j1-1][i2][j2-1][i3-1][j3],dp[i1][j1-1][i2][j2-1][i3][j3-1],dp[i1][j1-1][i2-1][j2][i3-1][j3],dp[i1][j1-1][i2-1][j2][i3][j3-1]);
if (i1==i2&&j1==j2&&i1==i3&&j1==j3) dp[i1][j1][i2][j2][i3][j3]+=a[i1][j1];
else
if (i1==i2&&j1==j2) dp[i1][j1][i2][j2][i3][j3]+=a[i1][j1]+a[i3][j3];
else
if (i1==i3&&j1==j3) dp[i1][j1][i2][j2][i3][j3]+=a[i1][j1]+a[i2][j2];
else
if (i2==i3&&j2==j3) dp[i1][j1][i2][j2][i3][j3]+=a[i1][j1]+a[i2][j2];
else dp[i1][j1][i2][j2][i3][j3]+=a[i1][j1]+a[i2][j2]+a[i3][j3];
}
cout<<dp[n][n][n][n][n][n];
return 0;
}

4维dp，考虑三条路径走相同步数（s）的状态可以避免在之后撞上其他路径在之前取过的数（因为两条路撞在一起的时候经过的步数必相同）
三条路所在的位置为(i,s-i),(j,s-j),(k,s-k)
（for循环，都可以for循环

#include<iostream>
using namespace std;
int f[45][25][25][25];
int main()
{
    int n;
    cin>>n;
    int v[25][25];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin>>v[i][j];
    
    f[0][0][0][0] = v[0][0];
    int dx[2] = {0, 1};
    int dy[2] = {1, 0};
    for (int s = 1; s <= 2*n-2; s++)
        for (int i = 0; i <= min(s, n-1); i++)
            for (int j = 0; j <= min(s,n-1); j++)
                for (int k = 0; k <= min(s, n-1); k++)
                {
                    for (int d1 = 0; d1 < 2; d1++)
                        for (int d2 = 0; d2 < 2; d2++)
                            for (int d3 = 0; d3 < 2; d3++)
                            {
                                int _i, _j, _k;
                                _i = i - dx[d1];
                                _j = j - dx[d2];
                                _k = k - dx[d3];
                                if (_i >= 0 && _i <= s && _j >=0 && _j <=s && _k >=0 && _k <=s)
                                {
                                    int tmp = v[i][s-i] + v[j][s-j] + v[k][s-k];
                                    if (i==j)
                                        tmp -= v[i][s-i];
                                    if (j==k)
                                        tmp -= v[j][s-j];
                                    if (i==k)
                                        tmp -= v[i][s-i];
                                    if (i==j && j==k)
                                        tmp += v[i][s-i];
                                    f[s][i][j][k] = max(f[s][i][j][k], f[s-1][_i][_j][_k] + tmp);
                                }
                            }
                }
    cout<<f[2*n-2][n-1][n-1][n-1];
    return 0;
}

四重DP

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
int n,ans;
int d[50][25][25][25],g[25][25];
inline int max8(int a,int b,int c,int d,int e,int f,int g,int h){
    return max(max(max(a,b),max(c,d)),max(max(e,f),max(g,h)));
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) cin>>g[i][j];
    for(int s=2;s<=n+n;s++){
        for(int i=1;i<s;i++){
            for(int j=1;j<s;j++){
                for(int k=1;k<s;k++){
                    d[s][i][j][k]=max8(d[s-1][i][j][k],d[s-1][i-1][j][k],d[s-1][i][j-1][k],d[s-1][i][j][k-1],d[s-1][i-1][j-1][k],d[s-1][i][j-1][k-1],d[s-1][i-1][j][k-1],d[s-1][i-1][j-1][k-1]);
                    d[s][i][j][k]+=g[s-i][i]+g[s-j][j]+g[s-k][k];
                    if(i==j) d[s][i][j][k] -= g[s-i][i];
                    else if(i==k) d[s][i][j][k] -= g[s-i][i];
                    else if(j==k) d[s][i][j][k] -= g[s-j][j];
                    if(i==j&&j==k) d[s][i][j][k] -= g[s-i][i];
                }
            }
        }
    }
    cout<<d[2*n][n][n][n];
    return 0;
}

拆点费用流
每个点只被取一次且可以被多次经过，感觉拆点比较好操作一些。
建边时候注意不能建到图的外面QAQ

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>

#define INF 2147483644

#define all ((n * n) + 10)

using namespace std;

const int Maxn = 5010;

struct node {
    int to, next, val, cap; 
} e[Maxn];

int a[110][110], n, tot = 1, h[Maxn], S, T, dis[Maxn], vis[Maxn], pre[Maxn];

void Add(int u, int v, int c, int p) {
    e[++tot] = (node){v, h[u],  c, p}; h[u] = tot;
    e[++tot] = (node){u, h[v], -c, 0}; h[v] = tot;
}

int num(int x, int y) {return (x - 1) * n + y;}

bool Bfs() {
    queue <int> Q;
    for(int i = S; i <= T + all; ++i) {
        dis[i] = -INF; vis[i] = 0; pre[i] = 0;
    }
    dis[S] = 0; Q.push(S);
    while(!Q.empty()) {
        int u = Q.front(); Q.pop(); vis[u] = 0;
        for(int i = h[u]; i; i = e[i].next) {
            int v = e[i].to;
            if(dis[v] < dis[u] + e[i].val && e[i].cap) {
                dis[v] = dis[u] + e[i].val;
                pre[v] = i;
                if(!vis[v]) {
                    vis[v] = 1;
                    Q.push(v);
                }
            }
        }
    }
    return dis[T + all] != -INF;
}

int Mcmf() {
    int temp = 0;
    while(Bfs()) {
        int s = INF;
        for(int i = pre[T + all]; i; i = pre[e[i ^ 1].to]) s = min(s, e[i].cap);
        for(int i = pre[T + all]; i; i = pre[e[i ^ 1].to]) e[i].cap -= s, e[i ^ 1].cap += s;
        temp += s * dis[T + all];
    } return temp;
}

int main() {
//  freopen("t.in", "r", stdin);
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) scanf("%d", &a[i][j]);
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            Add(num(i, j), num(i, j) + all, 0, 2);
            Add(num(i, j), num(i, j) + all, a[i][j], 1);
        }
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            if(i == n && j == n) continue;
            if(j < n) Add(num(i, j) + all, num(i, j + 1), 0, 3);
            if(i < n) Add(num(i, j) + all, num(i + 1, j), 0, 3);
        }
    }
    S = 0, T = num(n, n);
    Add(S, num(1, 1), 0, 3);
    printf("%d\n", Mcmf());
    return 0;
}

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int e[41][21][21][21];
int W[21][21];
int n;

inline int MAX(int a,int b,int c,int d,int e,int f,int g,int h)
{
    return max(a,max(b,max(c,max(d,max(e,max(f,max(g,h))))))); 
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            scanf("%d",&W[i][j]);
    e[1][1][1][1]=W[1][1];
    for(int x=1;x<n+n;++x)
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                for(int k=1;k<=n;++k)
                {
                    int i1=x-i+1;
                    int j1=x-j+1;
                    int k1=x-k+1;
                    if(i1<=0||j1<=0||k1<=0) continue;
                    int &NOW=e[x][i][j][k];
                    NOW=MAX(e[x-1][i-1][j][k],e[x-1][i][j-1][k],e[x-1][i][j][k-1],e[x-1][i-1][j-1][k],e[x-1][i][j-1][k-1],e[x-1][i-1][j][k-1],e[x-1][i-1][j-1][k-1],e[x-1][i][j][k])+W[i][i1]+W[j][j1]+W[k][k1];
                    if(i==j) NOW-=W[i][i1];
                    if(i==k) NOW-=W[i][i1];
                    if(j==k) NOW-=W[j][j1];
                    if(i==j&&j==k) NOW+=W[i][i1];
                }
    printf("%d",e[n+n-1][n][n][n]);
    
    return 0;
} 

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int f[41][21][21][21];
int map[21][21];
int N;
int main()
{
scanf("%d",&N);
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
scanf("%d",&map[i][j]);
}
}
f[1][1][1][1]=map[1][1];
for(int step=2;step<=2*N-1;step++){//枚举步数,假定走到 (1,1) 用了一步
for(int x1=max(1,step-N+1);x1<=min(N,step);x1++){//x1,x2,x3 是用 step步走到横坐标为 x1,x2,x3的方格,
for(int x2=max(1,step-N+1);x2<=min(N,step);x2++){//用min(),max()都是保证方格不越界的方式
for(int x3=max(1,step-N+1);x3<=min(N,step);x3++){
int delta=map[x1][step-x1+1]+map[x2][step-x2+1]+map[x3][step-x3+1];
if(x1==x2) delta-=map[x1][step-x1+1];
if(x1==x3) delta-=map[x1][step-x1+1];
if(x2==x3) delta-=map[x2][step-x2+1];
if(x1==x2&&x1==x3) delta+=map[x1][step-x1+1];//多减去了一次

f[step][x1][x2][x3]=max(f[step-1][x1][x2][x3],max(f[step-1][x1-1][x2][x3],
max(f[step-1][x1][x2-1][x3],max(f[step-1][x1][x2][x3-1],
max(f[step-1][x1-1][x2-1][x3],max(f[step-1][x1-1][x2][x3-1],
max(f[step-1][x1][x2-1][x3-1],f[step-1][x1-1][x2-1][x3-1])))))))+delta;

}
}
}
}
cout<<f[2*N-1][N][N][N];
return 0;
}

DP

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n;
int a[20+1][20+1];
int f[40+1][20+1][20+1][20+1];

int main()
{
    while (~scanf("%d",&n))
    {
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                scanf("%d",&a[i][j]);
        memset(f,0,sizeof(f));
        f[1][1][1][1]=a[1][1];
        for (int t=1;t<=2*n-1;t++)
            for (int i=1;i<=n;i++)
                for (int j=1;j<=n;j++)
                    for (int k=1;k<=n;k++)
                    {
                        int x[3+1]={0,i,j,k};
                        int y[3+1]={0,t-i+1,t-j+1,t-k+1};
                        if (y[1]>0&&y[2]>0&&y[3]>0)
                        {
                            int max_f=oo_min;
                            max_f=max(max_f,f[t-1][x[1]][x[2]][x[3]]);
                            max_f=max(max_f,f[t-1][x[1]-1][x[2]][x[3]]);
                            max_f=max(max_f,f[t-1][x[1]][x[2]-1][x[3]]);
                            max_f=max(max_f,f[t-1][x[1]][x[2]][x[3]-1]);
                            max_f=max(max_f,f[t-1][x[1]-1][x[2]-1][x[3]]);
                            max_f=max(max_f,f[t-1][x[1]-1][x[2]][x[3]-1]);
                            max_f=max(max_f,f[t-1][x[1]][x[2]-1][x[3]-1]);
                            max_f=max(max_f,f[t-1][x[1]-1][x[2]-1][x[3]-1]);
                            f[t][x[1]][x[2]][x[3]]=max(f[t][x[1]][x[2]][x[3]],max_f+a[x[1]][y[1]]+a[x[2]][y[2]]+a[x[3]][y[3]]);
                            if (x[1]==x[2])
                                f[t][x[1]][x[2]][x[3]]-=a[x[1]][y[1]];
                            if (x[1]==x[3])
                                f[t][x[1]][x[2]][x[3]]-=a[x[1]][y[1]];
                            if (x[2]==x[3])
                                f[t][x[1]][x[2]][x[3]]-=a[x[2]][y[2]];
                            if (x[1]==x[2]&&x[2]==x[3])
                                f[t][x[1]][x[2]][x[3]]+=a[x[1]][y[1]];
                        }
                    }
        printf("%d\n",f[2*n-1][n][n][n]);
    }
}

网络流 Min Cost Max Flow

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,m;
vector<int> f;
vector<int> e;
vector<int> u;
vector<int> pre;
vector<int> vis;
vector<vector<int> > a;
vector<vector<int> > c;
vector<vector<int> > p;
vector<vector<int> > ce;
vector<vector<int> > cw;
deque<int> q;

void add_edge_1(int x,int y,int c_v,int p_v)
{
    cw[x].push_back(y);
    c[x].push_back(c_v);
    p[x].push_back(p_v);
    ce[y].push_back(cw[x].size()-1);
    cw[y].push_back(x);
    c[y].push_back(0);
    p[y].push_back(-p_v);
    ce[x].push_back(cw[y].size()-1);
}

int bfs_1(int s,int t,int *flow,int *cost)
{
    f.resize(0);
    f.resize(cw.size(),0);
    f[s]=oo_max;
    e.resize(0);
    e.resize(cw.size(),-1);
    u.resize(0);
    u.resize(cw.size(),oo_max);
    u[s]=0;
    pre.resize(0);
    pre.resize(cw.size(),-1);
    pre[s]=s;
    vis.resize(0);
    vis.resize(cw.size(),0);
    for (q.resize(0),vis[s]=1,q.push_back(s);(!q.empty());vis[q.front()]=0,q.pop_front())
    {
        int now=q.front();
        for (int i=0;i<cw[now].size();i++)
            if (c[now][i]&&u[now]+p[now][i]<u[cw[now][i]])
            {
                f[cw[now][i]]=min(c[now][i],f[now]);
                e[cw[now][i]]=i;
                u[cw[now][i]]=u[now]+p[now][i];
                pre[cw[now][i]]=now;
                if (vis[cw[now][i]]==0)
                    vis[cw[now][i]]=1,q.push_back(cw[now][i]);
            }
    }
    (*flow)=f[t];
    (*cost)=u[t];
    return (pre[t]!=-1);
}

void min_cost_max_flow_1(int s,int t,int *flow,int *cost)
{
    int temp_flow,temp_cost;
    while (bfs_1(s,t,&temp_flow,&temp_cost))
    {
        for (int i=t;i!=s;i=pre[i])
            c[pre[i]][e[i]]-=temp_flow,c[i][ce[pre[i]][e[i]]]+=temp_flow;
        (*flow)+=temp_flow;
        (*cost)+=temp_cost;
    }
}

int main()
{
    //while (~scanf("%d%d",&n,&m))
    while ((~scanf("%d",&n))&&(m=3)>0)
    {
        a.resize(0);
        a.resize(n+1);
        for (int i=1;i<=n;i++)
        {
            a[i].resize(n+1,0);
            for (int j=1;j<=n;j++)
                scanf("%d",&a[i][j]);
        }
        int tot=n*n;
        cw.resize(0);
        cw.resize(2*tot+2);
        ce.resize(0);
        ce.resize(cw.size());
        c.resize(0);
        c.resize(cw.size());
        p.resize(0);
        p.resize(cw.size());
        for (int i=0;i<cw.size();i++)
        {
            cw[i].resize(0);
            ce[i].resize(0);
            c[i].resize(0);
            p[i].resize(0);
        }
        add_edge_1(0,1,m,0);
        add_edge_1(2*tot,cw.size()-1,m,0);
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
            {
                add_edge_1((i-1)*n+j,(i-1)*n+j+tot,1,-a[i][j]);
                add_edge_1((i-1)*n+j,(i-1)*n+j+tot,m,0);
                if (i>1)
                    add_edge_1((i-2)*n+j+tot,(i-1)*n+j,m,0);
                if (j>1)
                    add_edge_1((i-1)*n+j-1+tot,(i-1)*n+j,m,0);
            }
        int ans_flow=0,ans_cost=0;
        min_cost_max_flow_1(0,cw.size()-1,&ans_flow,&ans_cost);
        printf("%d\n",-ans_cost);
    }
}

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 41;
const int maxm = 22;
int dp[maxn][maxm][maxm][maxm];
int juzhen[maxm][maxm];
bool used[maxm][maxm];

int add_(int a,int b){
if(!used[a][b]){
used[a][b] = true;
return juzhen[a][b];
}
else return 0;
}

int main(){
memset(used,false,sizeof(used));
//memset(0,dp,sizeof(dp));
int n;
cin >> n;
for(int p = 1;p <= n;p++){
for(int q = 1;q <= n;q++) cin >> juzhen[p][q];
}
dp[2][1][1][1] = juzhen[1][1];
for(int p = 3;p <= 2*n;p++){
for(int i = 1;i < min(p,n + 1);i++){
if(p - i > n)continue;
for(int j = 1;j < min(p,n + 1);j++){
if(p - j > n)continue;
for(int k = 1;k < min(p,n + 1);k++){
if(p - k > n)continue;
//cout << " here" <<"\n";
int max_ = 0;
//rrr
if(i > 1 && j > 1 && k > 1){
max_ = max(max_,dp[p - 1][i - 1][j - 1][k - 1] + add_(p - i,i) + add_(p - j,j) + add_(p - k,k));
memset(used,false,sizeof(used));
}
// ddd
if(p - i > 1 && p - j > 1 && p - k > 1){
max_ = max(max_,dp[p - 1][i][j][k] + add_(p - i,i) + add_(p - j,j) + add_(p - k,k));
memset(used,false,sizeof(used));
}
// rrd
if(i > 1 && j > 1 && p - k > 1){
max_ = max(max_,dp[p - 1][i - 1][j - 1][k] + add_(p - i,i) + add_(p - j,j) + add_(p - k,k));
memset(used,false,sizeof(used));
}
// rdr
if(i > 1 && p - j > 1 && k > 1){
max_ = max(max_,dp[p - 1][i - 1][j][k - 1] + add_(p - i,i) + add_(p - j,j) + add_(p - k,k));
memset(used,false,sizeof(used));
}
//rdd
if(i > 1 && p - j > 1 && p - k > 1){
max_ = max(max_,dp[p - 1][i - 1][j][k] + add_(p - i,i) + add_(p - j,j) + add_(p - k,k));
memset(used,false,sizeof(used));
}
//ddr
if(p - i > 1 && p - j > 1 && k > 1){
max_ = max(max_,dp[p - 1][i][j][k - 1] + add_(p - i,i) + add_(p - j,j) + add_(p - k,k));
memset(used,false,sizeof(used));
}
//drd
if(p - i > 1 && j > 1 && p - k > 1){
max_ = max(max_,dp[p - 1][i][j - 1][k] + add_(p - i,i) + add_(p - j,j) + add_(p - k,k));
memset(used,false,sizeof(used));
}
//drr
if(p - i > 1 && j > 1 && k > 1){
max_ = max(max_,dp[p - 1][i][j - 1][k - 1] + add_(p - i,i) + add_(p - j,j) + add_(p - k,k));
memset(used,false,sizeof(used));
}
//cout << max_ <<"\n";
dp[p][i][j][k] = max_;
}
}
}
}
cout << dp[2*n][n][n][n] << "\n" << endl;
return 0;
}

再发一个网络流的题解，把MAX_CAPACITY改成任意正整数k，即可实现k取方格数
主要思路就是拆点构图。
把每个点 x 拆成 x1, x2，x1与x2之间有：
+ 一条容量为1，价值为x权值的边
+ 一条容量为MAX_CAPACITY，价值为0的边

假设y, z分别为 x 右侧、下方的点，把 x2 与 y1、x2 与 z1 各连一条边，容量为MAX_CAPACITY，价值为0
最后加上源点与汇点，最大费用流即可。我使用了SPFA寻找最长价值的路径。

解释一下变量含义：
+ edge类型中，next指向的是同一起点的下一条边在E中的位置
+ E是边集，size 是 E 的大小
+ headIndex[i] 指向的是起点为 i 的头一条边在E中的位置
+ used, dist, queue, prev 用于最长路算法，其中 prev[i] 记录最长路中通往点 i 的边在E中的位置

#include <stdio.h>
#include <stdlib.h>

#define NIL -1
#define MAX_CAPACITY 3
#define INF 10000000
#define MIN(a,b) ((a)<(b)?(a):(b))

typedef struct{
int next;
int from, to, value, f;
} edge;

edge E[5000];
int headIndex[1000];
int size = 0;

short used[1000];
int queue[10000];
int dist[1000];
int prev[1000];

void addEdge1(int from, int to, int value, int capacity);
void addEdge(int from, int to, int value, int capacity);
int maxPath(int source, int sink, int numV);
int maxValueFlow(int source, int sink, int numV);

int main(){
int n, numV;
int x, y, source, sink, value;

scanf("%d", &n);

/*initialize*/
for(x=0; x<1000; x++)
headIndex[x] = NIL;

/*build the network*/
numV = 0;
for(x=0; x<n; x++){
for(y=0; y<n; y++){
scanf("%d", &value);
addEdge(numV, numV+1, value, 1); //connect numV & numV+1
addEdge(numV, numV+1, 0, MAX_CAPACITY);
if(x < n-1)
addEdge(numV+1, numV+2*n, 0, MAX_CAPACITY); //connnect numV+1 & its downer neighbour, if exists
if(y < n-1)
addEdge(numV+1, numV+2, 0, MAX_CAPACITY); //connnect numV+1 & its righter neighbour, if exists
numV += 2;
}
}
source = numV, sink = numV+1;
addEdge(source, 0, 0, MAX_CAPACITY); //source
addEdge(numV-1, sink, 0, MAX_CAPACITY); //sink

/*solve*/
printf("%d\n", maxValueFlow(source, sink, numV+2));
return 0;
}
void addEdge1(int from, int to, int value, int capacity){
E[size].from = from;
E[size].to = to;
E[size].value = value;
E[size].f = capacity;
E[size].next = headIndex[from];
headIndex[from] = size;
size++;
}
void addEdge(int from, int to, int value, int capacity){
addEdge1(from, to, value, capacity);
addEdge1(to, from, -value, 0);
}
int maxPath(int source, int sink, int numV){
int i, head = 0, tail = 0;
for(i=0; i<numV; i++){
used[i] = 0;
prev[i] = NIL;
dist[i] = -INF;
}
dist[source] = 0;
queue[tail++] = source;
while(head < tail){
source = queue[head];
used[source] = 0;
i = headIndex[source];
while(i != NIL){
if(E[i].f > 0 && dist[E[i].to] < dist[source] + E[i].value){
dist[E[i].to] = dist[source] + E[i].value;
prev[E[i].to] = i;
if(!used[E[i].to]){
queue[tail++] = E[i].to;
used[E[i].to] = 1;
}
}
i = E[i].next;
}
head++;
}
return dist[sink];
}
int maxValueFlow(int source, int sink, int numV){
int path, v, augment, value, ret = 0;
while((value = maxPath(source, sink, numV)) > 0){
augment = INF;
for(v=sink; v!=source; ){
path = prev[v];
augment = MIN(augment, E[path].f);
v = E[path].from;
}
for(v=sink; v!=source; ){
path = prev[v];
E[path].f -= augment;
E[path^1].f += augment;
v = E[path].from;
}
ret += value*augment;
}
return ret;
}

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int f[21][21][21][21][21][21];
int map[21][21];
inline int max(int a,int b)
{
    return a>b? a:b;
}
inline int maxx(int a,int b,int c,int d,int e,int f,int g,int h){
    a=max(a,b);
    a=max(a,c);
    a=max(a,d);
    a=max(a,e);
    a=max(a,f);
    a=max(a,g);
    a=max(a,h);
    return a;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&map[i][j]);
        }
    for(int z=1;z<=n;z++)
        for(int x=1;x<=n;x++)
            for(int c=1;c<=n;c++)
                for(int v=1;v<=n;v++)
                    for(int b=1;b<=n;b++)
                        for(int m=1;m<=n;m++)
                        {
                            f[z][x][c][v][b][m]=maxx(f[z-1][x][c-1][v][b-1][m],f[z-1][x][c-1][v][b][m-1],f[z-1][x][c][v-1][b-1][m],f[z][x-1][c-1][v][b-1][m],f[z-1][x][c][v-1][b][m-1],f[z][x-1][c-1][v][b][m-1],f[z][x-1][c][v-1][b-1][m],f[z][x-1][c][v-1][b][m-1])+map[z][x]+map[c][v]+map[b][m];
                            if(z==c&&c==b&&x==v&&v==m)f[z][x][c][v][b][m]-=2*map[z][x];
                            else if(z==c&&x==v)f[z][x][c][v][b][m]-=map[z][x];
                            else if(z==b&&x==m)f[z][x][c][v][b][m]-=map[z][x];
                            else if(c==b&&v==m)f[z][x][c][v][b][m]-=map[c][v];
                        }
    printf("%d",f[n][n][n][n][n][n]);
    return 0;
}

谢谢大佬的inline，比之前走方格多了2维，以为会爆了。。。。（判断好长。。。）

ORZ 楼下 inline 真神奇

#include<iostream>
#include<cstring>
using namespace std;
inline int max(int a,int b){
return a>b? a:b;
}
const int maxn = 21;
inline int max(int a,int b,int c,int d,int e,int f,int g,int h){
a=max(a,b);
a=max(a,c);
a=max(a,d);
a=max(a,e);
a=max(a,f);
a=max(a,g);
a=max(a,h);
return a;
}
int dp[maxn][maxn][maxn][maxn][maxn][maxn];
int map[maxn][maxn];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>map[i][j];
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
for(int l=1;l<=n;l++)
for(int o=1;o<=n;o++)
for(int u=1;u<=n;u++)
{
dp[i][j][k][l][o][u]=max(dp[i-1][j][k-1][l][o-1][u],dp[i-1][j][k-1][l][o][u-1],dp[i][j-1][k-1][l][o-1][u],dp[i][j-1][k-1][l][o][u-1],dp[i-1][j][k][l-1][o-1][u],dp[i-1][j][k][l-1][o][u-1],dp[i][j-1][k][l-1][o-1][u],dp[i][j-1][k][l-1][o][u-1])+map[i][j]+map[k][l]+map[o][u];
if(i==k&&j==l&&!(k==o&&l==u&&i==o&&j==u&&i==k&&j==l)) dp[i][j][k][l][o][u]-=map[i][j];
if(k==o&&l==u&&!(k==o&&l==u&&i==o&&j==u&&i==k&&j==l)) dp[i][j][k][l][o][u]-=map[o][u];
if(i==o&&j==u&&!(k==o&&l==u&&i==o&&j==u&&i==k&&j==l)) dp[i][j][k][l][o][u]-=map[o][u];
if(k==o&&l==u&&i==o&&j==u&&i==k&&j==l) dp[i][j][k][l][o][u]-=2*map[o][u];
}
cout<<dp[n][n][n][n][n][n];
return 0;
}


丑陋的六维DP。
能过简直奇迹。
刚开始TLE，重载了max套了个inline就AC，时间平均800ms一个点。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<cmath>
#include<vector>
#include<sstream>
#define inf 0x3f3f3f3f
#define Rep(i,n) for(register int i = 1;i<=n;i++)
using namespace std;

short f[21][21][21][21][21][21];
inline short max(short a,short b){
    return a>b?a:b;
}
int main(){
    int n,a[21][21];
    scanf("%d",&n);
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=n;j++)scanf("%d",&a[i][j]);
    memset(f,0,sizeof(f));
    int m1,m2,m3,m4;
    Rep(i,n)
        Rep(j,n)
            Rep(p,n)
                Rep(q,n)
                    Rep(u,n)
                        Rep(v,n){
                            m1 = max(f[i-1][j][p-1][q][u-1][v],f[i-1][j][p-1][q][u][v-1]);
                            m2 = max(f[i-1][j][p][q-1][u-1][v],f[i-1][j][p][q-1][u][v-1]);
                            m3 = max(f[i][j-1][p][q-1][u-1][v],f[i][j-1][p][q-1][u][v-1]);
                            m4 = max(f[i][j-1][p-1][q][u-1][v],f[i][j-1][p-1][q][u][v-1]);
                            f[i][j][p][q][u][v] = max(max(m1,m2),max(m3,m4));
                            if(i!=p&&i!=u&&p!=u&&j!=q&&j!=v&&q!=v)f[i][j][p][q][u][v] += a[i][j]+a[p][q]+a[u][v];
                            else if(i==p&&i==u&&p==u&&j==q&&j==v&&q==v)f[i][j][p][q][u][v] += a[i][j];
                            else if(i==p&&j==q)f[i][j][p][q][u][v]+=a[i][j]+a[u][v];
                            else f[i][j][p][q][u][v]+=a[i][j]+a[p][q];
                        }
    printf("%d\n",f[n][n][n][n][n][n]);
    return 0;
}

f[step][x1][x2][x3]表示第step步时选择x1x2x3的最优解。
循环的时候x从1到n，
用x=max(1,s-n+1) 其中1是防止x越界 s-n+1是防止y越界，
因为s=x+y-1所以y=s-x+1<=n所以s-n+1<=x
用x<=min(n,s) 是防止x越界

DP的时候 因为上一步可以是x也可以是x-1 为了防止错误需将f={0}

#include <cstdio>
#include <algorithm>
using std::max;
using std::min;

int n,A[25][25],f[50][25][25][25]={0};

int main(){
freopen("in.txt","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&A[i][j]);
f[1][1][1][1]=A[1][1];
for(int s=2;s<=2*n-1;s++)
for(int x1=max(1,s-n+1);x1<=min(n,s);x1++)
for(int x2=max(1,s-n+1);x2<=min(n,s);x2++)
for(int x3=max(1,s-n+1);x3<=min(n,s);x3++){
//s=x+y-1
int add=A[x1][s-x1+1]+A[x2][s-x2+1]+A[x3][s-x3+1];
if(x1==x2) add-=A[x1][s-x1+1];
if(x1==x3) add-=A[x1][s-x1+1];
if(x2==x3) add-=A[x2][s-x2+1];
if(x1==x2&&x2==x3) add+=A[x1][s-x1+1];//容斥原理
f[s][x1][x2][x3]=max(f[s-1][x1][x2][x3],max(f[s-1][x1][x2][x3-1],max(f[s-1][x1][x2-1][x3],max(f[s-1][x1][x2-1][x3-1],max(f[s-1][x1-1][x2][x3],max(f[s-1][x1-1][x2][x3-1],max(f[s-1][x1-1][x2-1][x3],f[s-1][x1-1][x2-1][x3-1])))))));
f[s][x1][x2][x3]+=add;
}
printf("%d",f[2*n-1][n][n][n]);

return 0;
}

我爱压行

#include<iostream>
using namespace std;
int f[45][25][25][25],map[22][22];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>map[i][j];
int step=2*n-1;
for(int k=1;k<=step;k++)
for(int i=1;i<=min(k,n);i++)//min必须加，开始没加只过了五组。因为当k<n时，3个人
for(int j=1;j<=min(k,n);j++)//的横坐标不可能走到n
for(int l=1;l<=min(k,n);l++)
{
int x=map[i][k-i+1]+map[j][k-j+1]+map[l][k-l+1];
if(i==j)x-=map[j][k-j+1];
if(j==l)x-=map[l][k-l+1];
if(i==l)x-=map[i][k-i+1];
if(j==i&&j==l)
x=map[i][k-i+1];
for(int x1=0;x1>=-1;x1--)
for(int x2=0;x2>=-1;x2--)
for(int x3=0;x3>=-1;x3--)
f[k][i][j][l]=max(f[k][i][j][l],f[k-1][i+x1][j+x2][l+x3]+x);
}
cout<<f[step][n][n][n];
}

max()嵌套有点丑，将就着看看吧
pascal
uses math;
var dp:array[0..21,0..21,0..21,0..21] of integer; //x1,y1,x2,x3
map:array[0..20,0..20] of integer;
n,x1,y1,x2,y2,x3,y3:integer;
begin
read(n);
for x1:=1 to n do
for y1:=1 to n do
read(map[x1,y1]);
for x1:=1 to n do
for y1:=1 to n do
for x2:=1 to x1 do
for x3:=1 to x1 do begin
y2:=x1+y1-x2;
y3:=x1+y1-x3;
//writeln(x1,' ',y1,' ',x2,' ',y2,' ',x3,' f',y3);
dp[x1,y1,x2,x3]:=max(
max(max(dp[x1-1,y1,x2,x3],
dp[x1-1,y1,x2,x3-1]),
max(dp[x1-1,y1,x2-1,x3],
dp[x1-1,y1,x2-1,x3-1])),
max(max(dp[x1,y1-1,x2,x3],
dp[x1,y1-1,x2,x3-1]),
max(dp[x1,y1-1,x2-1,x3],
dp[x1,y1-1,x2-1,x3-1])))+map[x1,y1];
if (x1<>x2) and (y1<>y2) then inc(dp[x1,y1,x2,x3],map[x2,y2]);
if (x1<>x3) and (y1<>y3) and (x2<>x3) and (y2<>y3) then
inc(dp[x1,y1,x2,x3],map[x3,y3]);
end;
write(dp[n,n,n,n]);
end.


DP

Block code

#include<cstdio>
#include<cstring>
int f[45][25][25][25];
int g[25][25];
int n;
int i,j;
int h,a,b,c;
int x;
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&g[i][j]);
memset(f,0,sizeof(f));
for(h=2;h<=2*n;h++)
for(a=1;a<h;a++)
for(b=1;b<h;b++)
for(c=1;c<h;c++)
{
x=g[a][h-a];
if((50*a+h-a)!=(50*b+h-b))
x+=g[b][h-b];
if((50*c+h-c)!=(50*a+h-a)&&(50*c+h-c)!=(50*b+h-b))
x+=g[c][h-c];
f[h][a][b][c]=f[h-1][a][b][c];
f[h][a][b][c]=max(f[h][a][b][c],f[h-1][a][b][c-1]);
f[h][a][b][c]=max(f[h][a][b][c],f[h-1][a][b-1][c]);
f[h][a][b][c]=max(f[h][a][b][c],f[h-1][a-1][b][c]);
f[h][a][b][c]=max(f[h][a][b][c],f[h-1][a][b-1][c-1]);
f[h][a][b][c]=max(f[h][a][b][c],f[h-1][a-1][b][c-1]);
f[h][a][b][c]=max(f[h][a][b][c],f[h-1][a-1][b-1][c]);
f[h][a][b][c]=max(f[h][a][b][c],f[h-1][a-1][b-1][c-1]);
f[h][a][b][c]+=x;
// printf("f[%d][%d][%d][%d][%d][%d]=%d\n",a,h-a,b,h-b,c,h-c,f[h][a][b][c]);
}
printf("%d",f[2*n][n][n][n]);
return 0;
}

果真6维过不了，只能拿50分。压缩成四维即可秒杀。
实在受不了那些丑陋的嵌套 MAX，所以发个可变长参数的 MAX以供参考。

short MAX(int total, ...){
int ret = 0, tmp;
va_list args;
va_start(args, total);
while(total--){
tmp = va_arg(args, int);
if(ret < tmp)
ret = tmp;
}
va_end(args);
return (short)ret;
}

使用时要包含 <stdarg.h> 这个头文件。调用时，第一个参数需填写总共有多少数要比较。如：MAX(5, a, b, c, d, e)