本文主要是介绍hdu4826（三维DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这是一个百度之星的资格赛第四题
题目链接：http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500
题意：从左上角的点到右上角的点，每个点只能走一遍，走的方向有三个：向上，向下，向右，求最大值。
咋一看像搜索题，先暴搜，TLE,然后剪枝，还是TLE.然后我就改方法，用DP来做，这题和普通dp相比，多个个向上走的状态，所以加一维。
程序和注释如下：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>
#include<math.h>#define inf 0x7fffffff
#define N 105
#define eps 1e-9
#define pi acos(-1.0)
#define P system("pause")
using namespace std;
int a[N][N],dp[N][N][3];//dp[][][0]：左->右 dp[][][1]:上->下 dp[][][2] 下->上
int n,m;
int fun(int a,int b,int c)
{int t;t = max(a,b);return max(t,c);
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);int t,z = 1;scanf("%d",&t); while(t--){int i,j;scanf("%d%d",&n,&m);for(i = 0; i < n; i++)for(j = 0; j < m; j++){scanf("%d",&a[i][j]);dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = -inf;}dp[0][0][0] = dp[0][0][1] = dp[0][0][2] = a[0][0];for(i = 1; i < n; i++)dp[i][0][0] = dp[i][0][1] = dp[i][0][2] = dp[i-1][0][0] + a[i][0]; for(i = 1;i < m; i++)//遍历列 {for(j = 0; j < n; j++)//左往右走dp[j][i][0] = max(dp[j][i][0],fun(dp[j][i-1][0],dp[j][i-1][1],dp[j][i-1][2]) + a[j][i]);for(j = 1; j < n; j++)//上往下走dp[j][i][1] = max(dp[j][i][1],fun(dp[j-1][i][0],dp[j-1][i][1],dp[j-1][i][2]) + a[j][i]);for(j = n-2; j >= 0; j--)//下往上走，但是这里要注意下，不能有dp[j+1][i][1],使得有通路dp[j][i][2] = max(dp[j][i][2],max(dp[j+1][i][0],dp[j+1][i][2]) + a[j][i]); }// for(i = 0; i < n; i++){//for(j = 0; j < m ;j++)// cout<<fun(dp[i][j][0],dp[i][j][1],dp[i][j][2])<<" ";//cout<<endl;}printf("Case #%d:\n",z++);printf("%d\n",fun(dp[0][m-1][0],dp[0][m-1][1],dp[0][m-1][2])); }// P; return 0;
}
这篇关于hdu4826（三维DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
