首页 > 代码库 > POJ 1088 滑雪(简单的记忆化dp)
POJ 1088 滑雪(简单的记忆化dp)
题目
又一道可以称之为dp的题目,虽然看了别人的代码,但是我的代码写的还是很挫,,,,,,
//看了题解做的简单的记忆化dp#include<stdio.h>#include<algorithm>#include<iostream>using namespace std;int mp[110][110],dp[110][110];int xx[]={1,-1,0,0};int yy[]={0,0,1,-1};int n,m;int dfs(int x,int y){ int ans=1; if(dp[x][y])return dp[x][y]; for(int i=0;i<4;i++) { int dx=xx[i]+x,dy=yy[i]+y; if(dx>=0&&dy>=0&&dx<n&&dy<m) { if(mp[dx][dy]>mp[x][y]) ans=max(ans,1+dfs(dx,dy)); } } dp[x][y]=ans; return ans;}int main(){ while(scanf("%d%d",&n,&m)!=EOF){ for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ scanf("%d",&mp[i][j]); dp[i][j]=0; } } for(int i=0;i<n;i++) for(int j=0;j<m;j++) dp[i][j]=dfs(i,j); int maxx=0; for(int i=0;i<n;i++) for(int j=0;j<m;j++) maxx=maxx>dp[i][j]? maxx:dp[i][j]; printf("%d\n",maxx); } return 0;}
POJ 1088 滑雪(简单的记忆化dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。