滑雪
Time Limit:1000MS |
|
Memory Limit:65536K |
Total Submissions:69151 |
|
Accepted:25509 |
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#include<iostream>
using namespace std;
#define NUMMAX 101
int v[NUMMAX][NUMMAX],R,C;
void getMax(int v[NUMMAX][NUMMAX],int &lNum,int &hNum){
int max=0,maxL,maxH;
for(int i=1;i<=R;i++){
for(int j=1;j<=C;j++){
if(v[i][j]>max){
max=v[i][j];
maxL=i;
maxH=j;
}
}
}
lNum=maxL;
hNum=maxH;
}
int dp(int i,int j){
bool flag=false;
int maxL,maxH,max=0;
for(int k=i-1;k<=i+1;k++){
for(int l=j-1;l<=j+1;l++){
if(k>=1&&l>=1&&k<=R&&l<=C){
if(v[k][l]<v[i][j]&&v[k][l]>max){
flag=true;
max=v[k][l];
maxL=k;
maxH=l;
}
}
}
}
if(flag==false)
return 0;
else
return 1+dp(maxL,maxH);
}
int main(){
int i,j;
cin>>R>>C;
for(i=1;i<=R;i++){
for(j=1;j<=C;j++){
cin>>v[i][j];
}
}
int maxL,maxH;
getMax(v,maxL,maxH);
cout<<dp(maxL,maxH)+1;
system("pause");
}
这一道题相对十分简单,是dp中最简单的一种了,不多说了
分享到:
相关推荐
ACM PKU 1088 滑雪 答案 通过了测试已经,并附有分析。
pku acm 第1088题 滑雪c代码,含有详细注释,算法:动态规划
动态规划算法poj1088滑雪实验报告 动态规划算法poj1088滑雪实验报告
通过类似状态转移的方式进行深度优先的搜索查找来确定深度。
poj 1088 滑雪 代码,记忆化搜索
百练POJ1088滑雪问题的源代码,C写的,不过后缀是.cpp。写的还算比较易懂,呵呵
POJ上1088号的滑雪问题,需要的赶紧收藏了吧。递归典范
poj_1088 滑雪 lei.cpp是AC得代码 wang.cpp是wrong answer代码 in.cpp是随机产生测试数据的代码 *.bat是对比脚本
坐标型动态规划 poj1191棋盘分割 poj1088滑雪 noi过河卒 动态规划的解题思想及思路
包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku acm 1014 Dividing Pku acm 1050 To the Max Pku acm 1088 滑雪 Pku acm 2533 Longest ...