Pku_acm_1088 滑雪 .

滑雪
Time Limit:1000MS Memory Limit:65536K
Total Submit:6256 Accepted:1796

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

分析:

用回溯法,思路还是比较简单地,但是会超时,不知道有什么其他的办法

for each 可能的start point:

从该点回溯分析最长的下降路径

代码如下

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <vector>

#include <assert.h>

#include <math.h>

using namespace std;

//#define PI 3.1415926

//#define DBG

namespace Baidu09_3

{

struct Row{

int data[100];

};

vector <Row> vGraph;

struct Path{

int r;

int c;

int h;

};

vector <Path> vPath;

vector <Path> vPathMax;

void Test(vector <Row> &vGraph, int R, int C, int r, int c)

{

int dir[4][2]={

{0,1},

{0,-1},

{1,0},

{-1,0},

};

bool canGo =false;

for (int i=0; i<4; i++)

{

int r1=r+dir[i][0];

int c1=c+dir[i][1];

if(r1>=0 && r1<R && c1>=0 && c1<C && vGraph[r1].data[c1]<vGraph[r].data[c])

{

canGo = true;

Path path = {r1, c1, vGraph[r1].data[c1]};

vPath.push_back(path);

Test(vGraph,R,C,r1,c1);

vPath.pop_back();

}

if(!canGo)

{

if(vPathMax.size()<vPath.size())

vPathMax = vPath;

/*printf("\n----%d\n",vPath.size());

for(size_t i=0; i<vPath.size(); i++)

printf("%d ", vPath[i].h);*/

}

int main()

{

int R,C;

scanf("%d%d", &R, &C);

vGraph.reserve(R);

for(int i=0; i<R; i++)

{

Row row;

for(int j=0; j<C; j++)

scanf("%d", &row.data[j]);

vGraph.push_back(row);

}

for(int i=0; i<R; i++)

{

for(int j=0; j<C; j++)

{

vPath.clear();

Path path = {i, j, vGraph[i].data[j]};

vPath.push_back(path);

Test(vGraph,R,C,i,j);

}

printf("%d\n",vPathMax.size());

for(size_t i=0; i<vPathMax.size(); i++)

printf("%d ", vPathMax[i].h);

return 0;

}

};

正确的方法是用动态规划,参考:

ACM PKU 1088 滑雪　经典的动态规划备忘录方法（记忆化搜索／Memory function ）

http://acm.pku.edu.cn/JudgeOnline/problem?id=1088

非常经典的一道动态规划题，AC的时候心情简直舒畅到了极点．
时间限制是1000MS，如果直接用DFS肯定超时的．
马上想到动归，
用opt[i][j]记录从点node[i][j]出发的最短路径（不算本身，只算延伸；也就是初始值为0）
状态转移方程opt[i][j]=max{ opt[i+1][j],opt[i-1][j],opt[i][j+1],opt[i][j-1] } +１　
也就是说，opt[i][j]的值等于从node[i][j]的上下左右四个方向出发所滑的最长值＋１；
而这道题并不是简单的动归，计算opt[i][j]的过程需要类似DFS的递归方法．这就是记忆化搜索．　

Problem Id:1088  User Id:lnmm
Memory:152K  Time:0MS
Language:C++  Result:Accepted

#include"stdio.h"
2

const int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
3

int r,c;//r和c分别是行和列
4

int node[101][101]; //放置每个坐标上的高度
5

int opt[101][101]; //放置从每个坐标出发的最优解
6

bool ok(int i,int j)
8

{
9

return (i>=1 && i<=r && j>=1 &&j<=c);
10

}
11

int dp(int i,int j)
15

{
16

int k;
17

if(opt[i][j]>0) return opt[i][j]; //如果已经计算出,直接返回
18

for(k=0;k<4;k++) //向四个方向延伸
19

{
20

if(ok(i+dx[k],j+dy[k])) //如果节点没有超出边界
21

if( node[i+dx[k]][j+dy[k]]<node[i][j] ) //满足滑雪条件
22

{
23

if( opt[i][j]< dp(i+dx[k],j+dy[k])+1 )
24

opt[i][j]=dp(i+dx[k],j+dy[k])+1;
25

}
26

}
27

return opt[i][j];
28

// if(ok(i+dx[k],j+dy[k])&&node[i+dx[k]][j+dy[k]]<node[i][j]&&opt[i][j]>dp(i+dx[k],j+dy[k])+1)
31

// opt[i][j]=dp(i+dx[k],j+dy[k])+1;
32

}
36

void main()
38

{
39

int max=0,i,j;
40

scanf("%d%d",&r,&c);
41

for(i=1;i<=r;i++)
43

for(j=1;j<=c;j++)
44

scanf("%d",&node[i][j]);
45

for(i=1;i<=r;i++)
46

for(j=1;j<=c;j++)
47

opt[i][j]=0;
48

for(i=1;i<=r;i++)
50

for(j=1;j<=c;j++)
51

if(max<dp(i,j))max=dp(i,j);
52

printf("%d",max+1);　　//输出值需要＋１　，因为在前面的计算中，每个点的初始值都是0
53

return ;
55

}
56

http://www.cppblog.com/AClayton/archive/2007/09/17/32336.aspx

Published on May 31, 2009 in categories

Pku_acm_1088 滑雪 .

ACM PKU 1088 滑雪 经典的动态规划备忘录方法（记忆化搜索／Memory function ）

ACM PKU 1088 滑雪　经典的动态规划备忘录方法（记忆化搜索／Memory function ）