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


25

 

分析:

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

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<&& c1>=0 && c1<&& 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] } +1    
也就是说,opt[i][j]的值等于从node[i][j]的上下左右四个方向出发所滑的最长值+1;
而这道题并不是简单的动归,计算opt[i][j]的过程需要类似DFS的递归方法.这就是记忆化搜索. 


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

 1#include"stdio.h"
 2const int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
 3int r,c;//r和c分别是行和列
 4int node[101][101]; //放置每个坐标上的高度
 5int opt[101][101]; //放置从每个坐标出发的最优解
 6
 7bool ok(int i,int j)
 8{
 9  return (i>=1 && i<=&& j>=1 &&j<=c);
10}

11
12
13
14int dp(int i,int j)
15{
16    int k;
17    if(opt[i][j]>0return 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
29
30//       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
33     
34
35}

36
37void main()
38{
39    int max=0,i,j; 
40    scanf("%d%d",&r,&c);
41
42    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
49    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);  //输出值需要+1 ,因为在前面的计算中,每个点的初始值都是0
53
54    return ;
55}

56

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

Powered by Jekyll and Theme by solid

本站总访问量