[NOIP2008] 传纸条

题意：

传送门

题解：

dp

可以看做是从起点出发走两条不同的路径到终点，设dp[i][j][k][l]，注意两个点（即前两维和后两维）要同时转移才能保证不走重复路径

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
#define N 52
using namespace std;

int n,m;
int dp[N][N][N][N],a[N][N];

int gi() {
  int x=0,o=1; char ch=getchar();
  while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
  if(ch=='-') o=-1,ch=getchar();
  while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
  return o*x;
}

int main() {
  n=gi(),m=gi();
  for(int i=1; i<=n; i++)
    for(int j=1; j<=m; j++)
      a[i][j]=gi();
  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++) 
        if(i!=k && j!=l) 
        dp[i][j][k][l]=max(dp[i-1][j][k-1][l],max(dp[i-1][j][k][l-1],max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1])))+a[i][j]+a[k][l];
  dp[n][m][n][m]=max(dp[n-1][m][n-1][m],max(dp[n-1][m][n][m-1],max(dp[n][m-1][n-1][m],dp[n][m-1][n][m-1])));
  printf("%d
", dp[n][m][n][m]);
  return 0;
}