- 浏览: 200269 次
- 性别:
- 来自: 武汉
-
文章分类
- 全部博客 (137)
- c++ (74)
- c++,算法,回溯 (2)
- DP问题。 (9)
- DP问题,0/1背包问题 (3)
- 数学问题 (6)
- 贪心算法 (10)
- 排序 (16)
- 数据结构 (7)
- 容器 (2)
- 模拟问题 (2)
- 水题 (8)
- 并查集 (3)
- 非技术 (2)
- 素数问题 (1)
- DFS (3)
- 二叉树 (1)
- 递归 (1)
- 图论 (5)
- 最小生成树 (5)
- 最短路径 (6)
- bell_flaod算法 (2)
- hash (3)
- 二分查找 (1)
- 搜索 (5)
- BFS (5)
- STL (3)
- 字符串hash (1)
- 拓扑排序 (1)
- 字典树 (4)
- 哈弗曼树 (1)
- KMP (7)
- 线段树 (9)
- 树状数组 (6)
- 全排列 (2)
- DP问题 (2)
- LCS (1)
- 最长不下降子序列 (2)
- 面试经验 (3)
题意:给出一个图,求图上的一条最长的下降路径。 思路:很经典的DP,求二维的最长下降子序列。用记忆化的搜索,构造以每个点为起点的最长下降路径,结合DP的状态方程:DP[i][j] = max(DP[i-1][j],DP[i+1][j],DP[i][j-1],DP[i][j+1]) + 1。(if map[i][j] > map[x][y] && (x,y) in the map)。 代码如下: #include<iostream>
using namespace std;
const int Max = 105;
int row, col;
int map[Max][Max]; // 记录图各点的高度。
int dp[Max][Max]; // 记录以各点为起点的最长下降路径的长度。
int dfs(int r, int c)
{
if(dp[r][c] != 0)
return dp[r][c]; // 若dp[r][c]不为0,则表示它已被访问。
int max = 1;
if(r + 1 <= row && map[r][c] > map[r + 1][c])
{
int len = dfs(r + 1, c) + 1;
if(len > max)
max = len;
}
if(r - 1 >= 1 && map[r][c] > map[r - 1][c])
{
int len = dfs(r - 1, c) + 1;
if(len > max)
max = len;
}
if(c + 1 <= col && map[r][c] > map[r][c + 1])
{
int len = dfs(r, c + 1) + 1;
if(len > max)
max = len;
}
if(c - 1 >= 1 && map[r][c] > map[r][c - 1])
{
int len = dfs(r, c - 1) + 1;
if(len > max)
max = len;
}
return map[r][c] = max;
}
int main()
{
int i, j;
cin >> row >> col;
for(i = 1; i <= row; i ++)
for(j = 1; j <= col; j ++)
cin >> map[i][j];
int ans = 0;
memset(dp, 0, sizeof(dp));
for(i = 1; i <= row; i ++)
for(j = 1; j <= col; j ++)
{
dp[i][j] = dfs(i, j); // 用记忆化搜索求出dp[i][j],同时也求出了其路径上的dp[x][y]。
if(dp[i][j] > ans)
ans = dp[i][j];
}
cout << ans << endl;
return 0;
}
发表评论
-
虚函数、纯虚函数、虚基类、抽象类、虚函数继承、虚继承
2013-08-29 14:34 816虚函数:虚函数是C++中用于实现多态(polymorphis ... -
排序算法总结
2013-05-17 11:00 821选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法, ... -
poj 3122
2012-12-11 19:51 853题意:作者要开一个生日party,他现在拥有n块高度都为1 ... -
poj 3273
2012-12-11 16:49 967题意:给你天数n,和每天需要花的钱,让你把这些天分成m份(每份 ... -
poj 1080
2012-08-03 16:12 1211题意: 给两串DNA序列,按照给定的方法找他们最大的相似 ... -
字典树学习材料
2012-05-30 14:29 952字典树,又称单词查找树,Trie树,是一种树形结构,典型应 ... -
poj 1159
2012-05-28 19:08 1429题目大意:给你一段字符串,让你求出在中间最少加入几个字符 ... -
poj 3176
2012-05-28 14:47 999大致题意: 输入一个n层的三角形,第i层有i个数,求从第 ... -
poj 1260
2012-05-28 09:54 1594题意解释: 有n个等级的珠宝,等级依次升高,等级越高价钱越高 ... -
poj 1836
2012-05-28 09:22 2696是POJ2533的扩展题。题意不难,令到原队列 ... -
poj 2533
2012-05-26 15:36 1250在做这道题目之前,首先让我们了解一下什么是LIS算法,LIS俗 ... -
poj 3267
2012-05-26 09:43 795从程序可以看出,第i个位置到L所删除的字符数,总是先取最坏情况 ... -
poj 1276
2012-05-25 16:20 2381题意: 这道题的意思是给你一堆钱,各种面值的都有,比 ... -
poj 1094
2012-05-25 13:54 1099题意:给出字母个数,和有限个有序对(a<b)求出能确定字 ... -
poj 3393
2012-05-23 17:00 1249大致题意: 科普文一篇,文章80%都是无用信息,因为 ... -
poj 3007
2012-05-14 10:21 973大致题意: 给定一个字符串,从任意位置把它切为两半, ... -
poj 3096
2012-05-10 21:09 985题意: 定义D-pairs表示取字符串s中相距为D的两个字母 ... -
poj 1426
2012-04-26 20:11 2158大致题意: 给出一个整数n,(1 <= n <= ... -
poj 1797
2012-04-24 15:05 1615题目大意是就是何处一个图,n个顶点和m条边,每个边都有最大承载 ... -
poj 1338
2012-04-23 10:20 1244题意:题目意思是求由2,3,5的乘积组成的数从大到小排列,从1 ...
相关推荐
百练POJ1088滑雪问题的源代码,C写的,不过后缀是.cpp。写的还算比较易懂,呵呵
标题中的“动态规划算法poj1088滑雪实验报告”指的是使用动态规划算法解决北京大学ICPC在线测评系统POJ中编号为1088的滑雪问题。这个问题旨在通过一个直观的应用实例,帮助学习者深入理解动态规划的概念,并熟练运用...
poj 1088 滑雪 代码,记忆化搜索
poj acm通过的水题 完美动态规划和递归的应用,欢迎查看分享
标题中的"poj1088和1091"指的是两个编程竞赛题目,它们来源于一个名为POJ(Programming Online Judge)的在线编程竞赛平台。POJ是一个供程序员提交代码并进行自动评测的系统,主要考察选手的算法设计和编程能力。 ...
这个问题是关于动态规划(Dynamic Programming, DP)的一个经典实例,被称作“POJ滑雪问题”。在编程竞赛网站POJ(Problemset Online Judge)上有编号为1088的题目,该题目的核心是通过递归算法寻找一个二维数组中的...
POJ10838(滑雪)代码,POJ10838(滑雪)代码
在POJ题目中,我们可以看到一些经典的算法题目,例如,动态规划的题目,例如,1037 A decorative fence、1050 To the Max、1088 滑雪等。这类题目需要程序员使用动态规划算法来解决问题。 此外,POJ题目还包括一些...
poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...
* 1088 滑雪:本题目使用动态规划来计算滑雪的最短距离。 * 1125 Stockbroker Grapevine:本题目使用动态规划来计算股票交易的最大收益。 * 1141 Brackets Sequence:本题目使用动态规划来计算括号序列的最长长度。 ...
在编程竞赛领域,题目"POJ_1088 滑雪"是一个经典的问题,参赛者们通过编写代码来解决这个挑战。这个问题的核心在于理解题意并设计出高效的算法。"lei.cpp"和"wang.cpp"是两位参赛者的解决方案,它们提供了不同的编程...
第 13 题:poj1088 滑雪 这道题目要求我们找到一个给定区域中的最长下降子序列。这道题目可以使用动态规划来解决。我们可以使用 Top-Down 动态规划来解决这个问题,即从问题的终止状态开始,逐步回溯到问题的初始...
在这个实验中,学生需要解决一道名为“滑雪”的问题,通过动态规划方法找到最短路径。 实验步骤包括: 1. 阅读并理解题目,明确问题的定义和目标。 2. 设计动态规划的递推公式,这个公式描述了如何从已知的子问题...
相关题目有:1037 A decorative fence、1050 To the Max、1088 滑雪、1125 Stockbroker Grapevine、1141 Brackets Sequence、1159 Palindrome、1160 Post Office、1163 The Triangle、1458 Common Subsequence、1579...