一、有两种思路:
1)根据记忆搜索(保存了最优值表格),在纯粹的递归思路里加入记忆表格。
2)先将高度排序,然后依次从点由低到高 计算 该点的最长路径长度。(因为当矮点不可能通过高点,而比当前矮的点都在之前计算好了)
--------------------------------------------
二、关于最优路径构建
将点的最大路径长度依赖的点的(dx,dy) 即 行、列的增量存储在一个表格中。
Language:
Default
滑雪
Time Limit: 1000MS |
|
Memory Limit: 65536K |
Total Submissions: 50449 |
|
Accepted: 18324 |
Description
Michael喜欢滑雪百这并不奇怪, 因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子 1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小。在上面的例子中,一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上,这是最长的一条。
Input
输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行,每行有C个整数,代表高度h,0<=h<=10000。
Output
输出最长区域的长度。
Sample Input
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
Sample Output
25
Source
SHTSC 2002
#include <stdio.h>
int r,c;
//#define MAX 102
int height[102][102];
int length[102][102];
int FindMaxLength(int i,int j)
{
if(length[i][j]>0)
return length[i][j];
int tmp1=0;
int tmp2=0;
int tmp3=0;
int tmp4=0;
//left
if(j>=2)
if(height[i][j-1]<height[i][j])
tmp1=1+FindMaxLength(i,j-1);
//right
if(j<=c-1)
if(height[i][j+1]<height[i][j])
tmp2=1+FindMaxLength(i,j+1);
//up
if(i>=2 )
if( height[i-1][j]< height[i][j])
tmp3=1+FindMaxLength(i-1,j);
//down
if(i<=r-1 )
if(height[i+1][j]<height[i][j])
tmp4=1+FindMaxLength(i+1,j);
int max=0;
if(tmp1>max)
{
max=tmp1;
}
if(tmp2>max)
{
max=tmp2;
}
if(tmp3>max)
{
max=tmp3;
}
if(tmp4>max)
{
max=tmp4;
}
return max;
}
int main()
{
scanf("%d",&r);
scanf("%d",&c);
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
{
scanf("%d",&height[i][j]);
length[i][j]=0;
}
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
{
length[i][j]=FindMaxLength(i,j);
}
int max=0;
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
{
if(length[i][j]>max)
{
max=length[i][j];
}
}
max=max+1;
printf("%d\n",max);
scanf("%d",&r);
return 0;
}
增加 最优路径的代码:
|
分享到:
相关推荐
标题中的“动态规划算法poj1088滑雪实验报告”指的是使用动态规划算法解决北京大学ICPC在线测评系统POJ中编号为1088的滑雪问题。这个问题旨在通过一个直观的应用实例,帮助学习者深入理解动态规划的概念,并熟练运用...
百练POJ1088滑雪问题的源代码,C写的,不过后缀是.cpp。写的还算比较易懂,呵呵
poj 1088 滑雪 代码,记忆化搜索
根据给定的信息,我们可以将这些知识点分为几个大类别:数据结构、图论、搜索算法、动态规划、数学问题以及字符串处理等。 ### 数据结构 #### 队列 - **题目示例**: - POJ 3295:考察队列的基本应用。 #### ...
标题“POJ3253-POJ3253-Fence Repair【STL优先队列】”指的是一个在线编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。该题目要求参赛者使用C++编程语言解决特定的问题,并且在解决方案中...
### POJ 分类题目知识点详解 #### 一、基本算法 **1. 枚举** - **定义**:枚举是一种通过尝试所有可能情况来解决问题的方法。 - **示例题目**: - poj1753 - poj2965 - **应用场景**:适用于问题规模较小或解决...
- **描述**:单维动态规划是最基本的形式,只涉及到一个状态维度的变化。 - **应用场景**:背包问题、序列问题等。 - **相关题目**: - POJ 2488 - POJ 3083 - POJ 3009 - POJ 1321 - POJ 2251 #### 2. 多维...
1. **状态转移方程**:设计复杂的动态规划状态转移方程(poj1191, poj1054, poj3280, poj2029, poj2948, poj1925, poj3034)。 2. **记忆化搜索**:结合动态规划和递归搜索(POJ3254, poj2411, poj1185)。 3. **...
- POJ 1276: 动态规划的变种 - **背包问题**:包括0-1背包、完全背包等。 - **示例题目**: - POJ 3267: 0-1背包问题 - POJ 1836: 完全背包问题 - POJ 1260: 多重背包问题 - POJ 2533: 背包问题的特殊应用 - *...
第 13 题:poj1088 滑雪 这道题目要求我们找到一个给定区域中的最长下降子序列。这道题目可以使用动态规划来解决。我们可以使用 Top-Down 动态规划来解决这个问题,即从问题的终止状态开始,逐步回溯到问题的初始...
根据提供的文件信息,我们可以分析出该段代码是用于解决POJ平台上的2314题的一种解决方案,主要涉及到了变量管理、表达式处理等方面。下面将详细解释代码中的关键概念和实现逻辑。 ### 关键概念解析 #### Variable...
在北大POJ初级阶段,动态规划的题目可能涵盖基础的最短路径问题、最长递增子序列、矩阵链乘法、剪枝操作等。解题报告通常会包含以下几个部分: 1. **问题描述**:明确阐述题目的具体要求,包括输入和输出格式。 2. ...
而My-POJ则是个人构建的POJ(Problem Set Online Judge)系统,它是开源的,允许用户根据自己的需求定制功能。My-POJ通常基于开源的OJ框架,如Acm-ICPC或 poj.org。通过部署My-POJ,你可以拥有一个私有的判题环境,...
文档还通过一个具体的实例——POJ1163数字三角形问题来演示动态规划的工作方式。在这个问题中,需要在数字构成的三角形中找到一条从顶点到底边的路径,并使路径上数字之和最大。由于路径的每个步骤只能向左下或右下...
标题中的"Super-Memo-poj3580.zip_memo"暗示了这是一个关于Super-Memo算法的编程解决方案,可能是为了解决某个特定问题,比如在POJ(Programming Online Judge)平台上提交的第3580题。Splay Trees是数据结构领域中...
- POJ 1860, POJ 3259, POJ 1062, POJ 2253, POJ 1125, POJ 2240 最短路径问题是图论中的经典问题,涉及到多种不同的算法,如Dijkstra算法适合非负权重的图,而Bellman-Ford算法则可以检测负权环的存在。 3. **...
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
西北工业大学 C 语言 POJ 题目及答案第七季 该文档提供了西北工业大学 POJ(Programming Online Judge)平台上的 C 语言编程题目及答案,共计 7 题,涵盖了基本数据类型、运算符、控制结构、函数和数组等 C 语言...
标题中的"poj1088和1091"指的是两个编程竞赛题目,它们来源于一个名为POJ(Programming Online Judge)的在线编程竞赛平台。POJ是一个供程序员提交代码并进行自动评测的系统,主要考察选手的算法设计和编程能力。 ...
POJ根据题目的特点将其分为多个类别,包括但不限于基础算法、数据结构、搜索算法、动态规划等。每个类别下面又细分了许多具体的子类别。这种细致的分类方式有助于初学者快速定位到自己感兴趣或者需要加强的部分进行...