HDU 2686 Matrix（双线程DP）

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=2686

题意：从矩阵的（1,1）到（n,n）再从（n,n）到（1,1）中间不经过重复的值，来回能走过的最大值是多少

思路：打个来回可以直接想成从2个人同时从(1,1)到(n,n)且不经过同一个位置

AC代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <cstring>
#include <climits>
#include <cmath>
#include <cctype>
const int inf = 0x3f3f3f3f;//1061109567
typedef long long LL;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
int map1[35][35];
int dp[35][35][35][35];
int main()
{
int n;
while(scanf("%d",&n) != EOF)
{
memset(dp,0,sizeof(dp));
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
scanf("%d",&map1[i][j]);
}
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
for(int k=i+1; k<=n; k++)
{
int l = i + j - k;//确定第二部的纵坐标
if(l <= 0)
break;
dp[i][j][k][l] = max(max(dp[i-1][j][k-1][l],dp[i][j-1][k][l-1]),max(dp[i-1][j][k][l-1],dp[i][j-1][k-1][l]));
dp[i][j][k][l] += map1[i][j] + map1[k][l];
}
}
}
printf("%d\n",dp[n-1][n][n][n-1]+map1[1][1]+map1[n][n]);
}
return 0;
}

大神写的三维的

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <cstring>
#include <climits>
#include <cmath>
#include <cctype>
const int inf = 0x3f3f3f3f;//1061109567
typedef long long LL;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
int map1[55][55];
int dp[110][55][55];
int main()
{
int n;
while(scanf("%d",&n) != EOF)
{
memset(dp,0,sizeof(dp));
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
scanf("%d",&map1[i][j]);
}
}
int k;
for(k=1; k<2*n-2; k++)
{
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
if(i==j)
continue;
dp[k][i][j] = max(max(dp[k-1][i][j],dp[k-1][i-1][j]),max(dp[k-1][i][j-1],dp[k-1][i-1][j-1]));
dp[k][i][j] += map1[i][k-i] + map1[j][k-j];
}
}
}
printf("%d\n",dp[k-1][n-1][n-2]+map1[0][0]+map1[n-1][n-1]);
}
return 0;
}