POJ1088 滑雪(DFS+简单DP)
http://poj.org/problem?id=1088
题意:给你一个R*C的数字矩阵,要你找出矩阵中一条递减的最长路径的长度.即从矩阵的一个点出发,只能走数字递减的上下左右4格中的一格,能走的最长距离(包括起点).
分析:
首先我们令len[r][c]表示从(r,c)点出发的最长路径长度.
可以知道如下状态转移方程:
len[r][c]= max(len[r+1][c], len[r-1][c], len[r][c-1],len[r][c+1])+1.
注意上面的方程转移的条件是(r,c)点的数字比它4个方向的数字都大,如果某个方向不满足该条件,则不可转移.
AC代码:记忆化搜索
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100+5;
int dr[]={-1,1,0,0};
int dc[]={0,0,-1,1};
int map[maxn][maxn];
int len[maxn][maxn];
int R,C;
int dp(int r,int c)
{
if(len[r][c]!=0) return len[r][c];
len[r][c]=1;
for(int d=0;d<4;d++)
{
int nr=r+dr[d], nc=c+dc[d];
if(nr<=0||nr>R||nc<=0||nc>C||map[nr][nc]>=map[r][c]) continue;
len[r][c]=max(dp(nr,nc)+1,len[r][c]);
}
return len[r][c];
}
int main()
{
while(scanf("%d%d",&R,&C)==2)
{
int ans=1;
memset(len,0,sizeof(len));
for(int i=1;i<=R;i++)
for(int j=1;j<=C;j++)
scanf("%d",&map[i][j]);
for(int i=1;i<=R;i++)
for(int j=1;j<=C;j++)
{
len[i][j]=dp(i,j);
ans=max(ans,len[i][j]);
}
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
动态规划算法poj1088滑雪实验报告 动态规划算法poj1088滑雪实验报告
POJ-2870 Light Up + DFS(1级DFS+1级DFS) + Python - 思维导图 链接:https://blog.csdn.net/xxdragon126/article/details/122095922?spm=1001.2014.3001.5501
百练POJ1088滑雪问题的源代码,C写的,不过后缀是.cpp。写的还算比较易懂,呵呵
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
poj 1088 滑雪 代码,记忆化搜索
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
poj 2488——dfs深度优先遍历 //给行数列数,求问能否遍历,给出字典序的一种遍历
NULL 博文链接:https://128kj.iteye.com/blog/1750462
poj1088原代码, 这是最新的版本, 经过我们dhuACM团队合作而编写的!
poj acm通过的水题 完美动态规划和递归的应用,欢迎查看分享
北大POJ初级-简单搜索 解题报告+AC代码
关于poj dp分类,我一直寻找dp的分类,终于找到了,也上传一下
POJ10838(滑雪)代码,POJ10838(滑雪)代码
坐标型动态规划 poj1191棋盘分割 poj1088滑雪 noi过河卒 动态规划的解题思想及思路
北大POJ1691-Painting A Board 【拓扑+DFS】 解题报告+AC代码
西北工业大学POJ试题C++答案代码+课程设计
POJ上1088号的滑雪问题,需要的赶紧收藏了吧。递归典范
这是我自己的理解写的代码,适合初学者看,代码不怎么简介,算法还是比较好的
Poj 3342 这是一道树状dp题目,题意是这样的,一个公司,每个人有且仅有一个Boss,除了最大的Boss没有Boss(显然),现在要参加一个聚会,要求参加的人数最多,但是棘手的.......