POJ1088 滑雪 && NYOJ 10 skiing 经典的动态规划练习题

Categories: 数据结构和算法
Comments: 1 Comment
Published on: 2011 年 03 月 16 日

http://acm.nyist.net/JudgeOnline/problem.php?pid=10

理解了十分简单,思路日下:用一个结构体存储位置和相应位置的高度,然后根据高度从低到高排序。之后就从第一个最小的数据开始处理,根据结构体中记录的位置向上下左右寻找排序后的第二个数据(即次小的数据),然后其滑行最远距离存储在一个相应的矩阵中,最后可轻易获取最长滑行距离。

#include<iostream>  
#include<vector>  
#include<string.h>  
#include<algorithm>  
using namespace std;  
int h[104][104];  
int l[104][104];  
struct len  
{  
    int x,y;  
    int max;  
};  
bool cmp(len p1, len p2)  
{  
    return p1.max<p2.max;  
}  
int main()  
{  
    int n;  
    cin>>n;  
    while(n--)  
    {  
        memset(h,0,sizeof(h));  
        memset(l,0,sizeof(l));  
        int r,c;  
        cin>>r>>c;  
        vector<len> vec;  
        len lm;  
        for (int i=1;i<=r;i++)  
            for (int j=1;j<=c;j++)  
            {  
                cin>>h[i][j];  
                lm.x=i;  
                lm.y=j;  
                lm.max=h[i][j];  
                vec.push_back(lm);  
            }  
        for (int i=0;i<=c;i++)  
        {  
            h[0][i]=11111;  
            h[r+1][i]=11111;  
            h[i][0]=11111;  
            h[i]1=11111;  
        }  
        sort(vec.begin(),vec.end(),cmp);  
        l[vec[0].x][vec[0].y]=0;  
        int max=-1;  
        for (int i=1;i<vec.size();i++)  
        {  
            int mm=-1;  
            int flog=0;  
            if ( h[vec[i].x][vec[i].y]>h[vec[i].x+1][vec[i].y] && mm<l[vec[i].x+1][vec[i].y])  
            {  
                mm=l[vec[i].x+1][vec[i].y];  
                flog=1;  
            }  
            if ( h[vec[i].x][vec[i].y]>h[vec[i].x-1][vec[i].y] && mm<l[vec[i].x-1][vec[i].y])  
            {  
                mm=l[vec[i].x-1][vec[i].y];  
                flog=1;  
            }  
            if ( h[vec[i].x][vec[i].y]>h[vec[i].x][vec[i].y+1] && mm<l[vec[i].x][vec[i].y+1])  
            {  
                mm=l[vec[i].x][vec[i].y+1];  
                flog=1;  
            }  
            if ( h[vec[i].x][vec[i].y]>h[vec[i].x][vec[i].y-1] && mm<l[vec[i].x][vec[i].y-1])  
            {  
                mm=l[vec[i].x][vec[i].y-1];  
                flog=1;  
            }  
            if (flog)  
                mm++;  
            else mm=0;  
            l[vec[i].x][vec[i].y]=mm;  
            if(max<mm) max=mm;  
        }  
        if(max+1!=0)  
        cout<<max+1<<endl;  
        else cout<<"1"<<endl;  
    }  
    return 0;  
}  

我猜你可能也喜欢:

1 Comment - Leave a comment
  1. alan说道:

    楼主。考虑如下矩阵 [10 9 10;6 8 9;7 9 9],按你的算法,6- 7- 9,长度为3,但是结果应该是10-9-8-6,长度为4。似乎还是深搜+递归才能解决。

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期二, 2017 年 10 月 24 日