首页 > 代码库 > 【UVA】10285-Longest Run on a Snowboard(动态规划)
【UVA】10285-Longest Run on a Snowboard(动态规划)
这题出简单了,不需要打印路径。
状态方程dp[i][j] = max(dp[i-1][j],dp[i][j-1],dp[i+1][j],dp[i][j+1]);
14003395 | 10285 | Longest Run on a Snowboard | Accepted | C++ | 0.026 | 2014-08-07 11:43:51 |
枚举每个点进行遍历,使用记忆化搜索。要不会超时。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<map> #include<set> #include<list> #include<string> #include<sstream> #include<ctime> using namespace std; #define _PI acos(-1.0) #define INF (1 << 10) #define esp 1e-6 typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pill; /*=========================================== ===========================================*/ #define MAXD 100 + 10 char name[MAXD]; int m,n,ans; int dp[MAXD][MAXD]; int mat[MAXD][MAXD]; int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}; int DP(int x,int y){ if(dp[x][y] != -1) return dp[x][y]; dp[x][y] = 1; for(int i = 0 ; i < 4 ; i++){ int _x = dir[i][0] + x; int _y = dir[i][1] + y; if(_x >= 0 && _y >=0 && _x < n && _y < m && mat[x][y] < mat[_x][_y]){ dp[x][y] = max(dp[x][y],DP(_x,_y) + 1); } } ans = max(ans,dp[x][y]); return dp[x][y]; } int main(){ int T; scanf("%d",&T); while(T--){ scanf("%s%d%d",name,&n,&m); int pos_x,pos_y; int MIN = INF; memset(dp,-1,sizeof(dp)); for(int i = 0 ; i < n ; i++) for(int j = 0 ; j < m ; j++){ scanf("%d",&mat[i][j]); if(mat[i][j] < MIN){ MIN = mat[i][j]; pos_x = i; pos_y = j; } } ans = 0; for(int i = 0 ; i < n ; i++) for(int j = 0 ; j < m ; j++) DP(i,j); printf("%s: %d\n",name,ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。