有一(n imes m)的网格图，每个网格有权值(w[i][j])，从（1,1）出发到（n，m）寻找两条只能向左走或者向下走的路径，取走每个网格的权值，每个网格的权值只能被取一次，询问最大的权值，(1≤m,n≤50)。
解
法一：
注意到只有两条路径，于是我们可以直接暴力枚举路径终点，故设(f[i][j][k][l])表示一条路径到（i，j），一条路径到（k，l）的权值最大值，故不难有转移
[f[i][j][k][l]=max(f[i-1][j][k-1][l],f[i-1][j][k][l-1],f[i][j-1][k-1][l],f[i][j-1][k][l-1])+w[i][j]+(i
eq k or j
eq l)w[k][l]
]
边界：全为0
答案：(f[n][m][n][m])
参考代码：
#include <iostream>
#include <cstdio>
#define il inline
#define ri register
using namespace std;
int w[51][51],jz[51][51][51][51];
il void read(int&);
template<class free>
il free Max(free,free);
int main(){
int m,n,i,j,k,l;
read(m),read(n);
for(i=1;i<=m;++i)
for(j=1;j<=n;++j)
read(w[i][j]);
for(i=1;i<=m;++i)
for(j=1;j<=n;++j)
for(k=1;k<=m;++k)
for(l=1;l<=n;++l){
jz[i][j][k][l]=Max(Max(jz[i-1][j][k-1][l],jz[i][j-1][k-1][l]),
Max(jz[i-1][j][k][l-1],jz[i][j-1][k][l-1]));
jz[i][j][k][l]+=w[i][j];if(i!=k||j!=l)jz[i][j][k][l]+=w[k][l];
}printf("%d",jz[m][n][m][n]);
return 0;
}
template<class free>
il free Max(free a,free b){
return a>b?a:b;
}
il void read(int &x){
x&=0;ri char c;while(c=getchar(),c==' '||c=='
'||c=='
');
ri bool check(false);if(c=='-')check|=true,c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
if(check)x=-x;
}
法二：
注意到网格行走问题的步数一致的性质，故设(f[i][j][k])表示路径到第i步，路径1在第j行，路径2在第k行，根据规律不难知路径一在i+1-j列,同理路径2在i+1-k,于是不难有转移
[f[i][j][k]=max(f[i][j][k],f[i][j-1][k],f[i][j][k-1],f[i][j-1][k-1])+w[j][i+1-j]+(j
eq l)w[k][i+1-j]
]
边界：全为0
答案：(f[n+m-2][n][m])
参考代码：
#include <iostream>
#include <cstdio>
#define il inline
#define ri register
using namespace std;
int w[51][51],dp[101][101][101];
il void read(int&);
template<class free>
il free Max(free,free);
int main(){
int m,n,li;read(m),read(n);
for(int i(1),j;i<=m;++i)
for(j=1;j<=n;++j)read(w[i][j]);
li=m+n-2;
for(int i(1),j,k;i<=li;++i)
for(j=1;j<=m&&j<=i+1;++j)
for(k=1;k<=m&&k<=i+1;++k){
dp[i][j][k]=Max(Max(dp[i-1][j][k],dp[i-1][j-1][k]),
Max(dp[i-1][j-1][k-1],dp[i-1][j][k-1]));
dp[i][j][k]+=w[j][i+2-j];if(j!=k)dp[i][j][k]+=w[k][i+2-k];
}printf("%d",dp[li][m][m]);
return 0;
}
template<class free>
il free Max(free a,free b){
return a>b?a:b;
}
il void read(int &x){
x&=0;ri char c;while(c=getchar(),c<'0'||c>'9');
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}