菜鸡的题解018——传纸条

双线程DP问题，

f[i][j][k][l]代表a走到i，j位置，b走到k，l位置的最大值。状态转移方程：

f[i][j][k][l]=max(max(max(f[i-1][j][k-1][l],f[i][j-1][k-1][l]),f[i-1][j][k][l-1]),f[i][j-1][k][l-1])+a[i][j]+a[k][l];

为避免两张纸条传到同一个位置：

if(i==k&&j==l)f[i][j][k][l]-=a[i][j];

参考代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
#include<set>
#include<sstream>
#include<cstring>
#include<utility>
using namespace std;
typedef long long ll;
typedef long l;
const int N = 55;
int n,m,a[55][55],f[N][N][N][N];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int k=1;k<=n;k++){
				for(int l=1;l<=m;l++){
					f[i][j][k][l]=max(max(max(f[i-1][j][k-1][l],f[i][j-1][k-1][l]),f[i-1][j][k][l-1]),f[i][j-1][k][l-1])+a[i][j]+a[k][l];
					if(i==k&&j==l)f[i][j][k][l]-=a[i][j];
				}
			}
		}
	}
	cout<<f[n][m][n][m];
}