动态规划解决skiing问题

2024-04-11 10:38

本文主要是介绍动态规划解决skiing问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

描述

Michael喜欢滑雪百这并不奇怪,因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子 1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小。在上面的例子中,一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上,这是最长的一条。

输入

第一行表示有几组测试数据,输入的第二行表示区域的行数R和列数C(1 <= R,C<= 100)。下面是R行,每行有C个整数,代表高度h0<=h<=10000后面是下一组数据;

输出

输出最长区域的长度。

样例输入

1

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

样例输出

25

 

分析:

      从题目要求来看,枚举肯定是不行的。剩下能想的有递归和动态规划。当时提交的是DP,写完后查阅了下资料,发现使用递归算法居多。特此记录下,使用动态规划的算法解决滑雪问题。

      这里的动态规划,可以理解为牺牲存储空间,换取时间资源。在本题中,先初始化所有点的各种信息值,如沿着某点最多可以滑行的长度count。初始化后,就可以进行动态规划。从最低的点A开始,记录它周围比它低的点的个数count。然后找到数值比A大的最近的点B,找到B周围所有比它低的点,然后比较所有点的count值,将最大的count1作为Bcount

      上面的描述只是一个大概的思想,实施起来,还需要解决一些问题。比如,如何找到点A大的最近的点,找到该点后,又需要对它周围的点进行类似的处理。这种思想,给人使用递归的冲动。实际上,我们只需要把所有的位置点从小到大排序起来,依次记录该点的坐标,高度,该点起最大的滑行长度等信息。

      这样就很自然地构造出了一个数据结构

struct MyPoint
{int i,j;int height;int val;
};

上面提到了按照高度进行排序,再进行其他的处理。在C++STL中,有一个sort函数可提供排序功能,并且支持自定义的函数比较。我们只需要定义一个比较高度的函数即可。

bool less_height(const MyPoint & m1, const MyPoint & m2)
{return m1.height< m2.height;
}


方向的遍历

      当对一个点的四周进行遍历时,虽然可以直接一个一个地引用下标,来读取周围点的信息,但我们有一种更好的实现方式。在这里我们定义一个数组存储自定义的结构体,表示周围点的方向矢量。

      为了实现这一点,我们首先定义点的结构体

struct Pt
{int x, y;
}


 

定义完结构体后,我们就按上右下左的顺序,把周围点的方向矢量放到Direction数组中

Pt direction[4]={{-1,0},{0,1},{1,0},{0,-1}};  


 

完整代码:

#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
using namespace std;struct MyPoint
{int i,j;int height;int val;
};
struct Pt
{int x;int y;
};
bool less_height(const MyPoint & m1, const MyPoint & m2)
{return m1.height< m2.height;
}
int main()
{MyPoint mp;vector<MyPoint> v;int max;int i ,j ,m ,n ,N;int x,y;//定以矩阵,0表示高度,1表示路径长度int data[100][100][2];Pt direction[4]={{-1,0},{0,1},{1,0},{0,-1}};    cin>>N;while(N--){v.clear();cin>>m>>n;//初始化矩阵for(i=0; i<m; ++i)for(j=0; j<n; ++j){data[i][j][0]=0;data[i][j][1]=0;}for(i=0; i<m; ++i)for(j=0; j<n; ++j){mp.i=i,mp.j=j;mp.val=0;cin>>mp.height;data[i][j][0]=mp.height;v.push_back(mp);}int k=0;sort(v.begin(), v.end(), less_height);for(i=0; i<v.size(); ++i){int t;max=0;for(t=0; t<4; ++t){x=v[i].i + direction[t].x;y=v[i].j + direction[t].y;//越界检查if(x<0 || x>=m || y<0 || y>=n)continue;if(data[x][y][0]<v[i].height && data[x][y][1]>max){max = data[x][y][1];}}x=v[i].i; y=v[i].j;v[i].val = max+1;data[x][y][1]=v[i].val;}max=0;for(i=0; i<m; ++i){for(j=0; j<n; ++j)if(data[i][j][1]>max)max=data[i][j][1];}cout<<max<<endl;}return 0;
}




这篇关于动态规划解决skiing问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/893842

相关文章

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

如何解决线上平台抽佣高 线下门店客流少的痛点!

目前,许多传统零售店铺正遭遇客源下降的难题。尽管广告推广能带来一定的客流,但其费用昂贵。鉴于此,众多零售商纷纷选择加入像美团、饿了么和抖音这样的大型在线平台,但这些平台的高佣金率导致了利润的大幅缩水。在这样的市场环境下,商家之间的合作网络逐渐成为一种有效的解决方案,通过资源和客户基础的共享,实现共同的利益增长。 以最近在上海兴起的一个跨行业合作平台为例,该平台融合了环保消费积分系统,在短

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库,瞬间耗尽数据库资源,导致数据库无法使用。 解决方案: 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内,大量缓存数据同时失效,导致所有请求直接涌向数据库,瞬间增加数据库的负载压力,可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl