uva 10285 - Longest Run on a Snowboard 记忆化搜索+dp
题目链接：
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1226
题目意思：
给一张方格，求出一条最长的路径，要求路径上下一点的值小于上一点。
解题思路：
记忆化搜索+dp。‘
代码：
//记忆化搜索+dp#include<iostream>#include<cmath>#include<cstdio>#include<cstdlib>#include<string>#include<cstring>#include<algorithm>#include<vector>#include<map>#include<stack>#include<queue>#define eps 1e-6#define INF (1<<20)#define PI acos(-1.0)using namespace std;int dp[120][120],save[120][120];int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}}; //四个方向int m,n;//dp[i][j]表示从位置为i,j处出发所得到的最长的路径长度bool issure(int i,int j) //判断是否越界{ if(i<1||i>m||j<1||j>n) return false; return true;}int dfs(int row,int column) //dfs的返回值为从该点出发的最长路径长度{ if(dp[row][column]) //如果前面计算某一条路时已经计算出了，直接返回 return dp[row][column]; int temp=0; for(int i=0;i<4;i++) //从四个方向扫描 { int tempi=row+dir[i][0],tempj=column+dir[i][1]; if(issure(tempi,tempj)&&save[tempi][tempj]<save[row][column]) //不用记录是否访问过该点，因为总是沿着小于该点值的方向走 temp=max(dfs(tempi,tempj),temp); } dp[row][column]=temp+1; //加上该点，也算一个 //printf("*%d\n",dp[row][column]); return dp[row][column];}int main(){ int ca; char name[30]; scanf("%d",&ca); while(ca--) { scanf("%s%d%d",name,&m,&n); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) scanf("%d",&save[i][j]); int ans=0; memset(dp,0,sizeof(dp)); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) { if(dp[i][j]==0) //如果没有计算 { ans=max(ans,dfs(i,j)); } else ans=max(ans,dp[i][j]); //已经计算出了 } printf("%s: %d\n",name,ans); //输出 } return 0;}/*Feldberg 10 556 14 51 58 8826 94 24 39 4124 16 8 51 5176 72 77 43 1038 50 59 84 815 23 37 71 7796 10 93 53 8294 15 96 69 974 0 62 38 9637 54 55 82 38*//*kjlj 5 51 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9*/