首页 > 代码库 > POJ1088:滑雪（简单dp)
POJ1088:滑雪（简单dp)
题目链接： http://poj.org/problem?id=1088
题目要求： 一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。求可以滑落的最长长度。
题目解析：
首先要先排一下序，因为只能高度递减才能滑行。之后就很简单了，就是简单DP。
即：要求的滑坡是一条节点递减并依次相邻的最长路径，可以先根据高度将所有的点进行排序，在i点的时候，遍历0~i-1个点(升序排序，i前面的点的高度一定小于等于i),取相邻点间的大的路径长度
代码如下：
#include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>#include <queue>#include <math.h>#define N 400#define inf 0x3f3f3f3ftypedef int ll;using namespace std;int tt;struct node{ int h,l,w,dp;}q[20010];int cmp(const void *a,const void *b){ struct node *aa=(struct node *)a; struct node *bb=(struct node *)b; return aa->w-bb->w;}int main(){ int R,C,mat; while(scanf("%d%d",&R,&C)!=EOF) { tt=0; mat=1; for(int i=1;i<=R;i++) { for(int j=1;j<=C;j++) { scanf("%d",&q[tt].w); q[tt].h=i; q[tt].dp=1;//初始值为1 q[tt++].l=j; } } qsort(q,tt,sizeof(q[0]),cmp); for(int i=1;i<tt;i++) { int rr=q[i].h; int ll=q[i].l; for(int j=0;j<i;j++) { int r2=q[j].h; int l2=q[j].l; if((q[i].w>q[j].w)&&((abs(r2-rr)==1&&ll==l2)||(rr==r2&&abs(ll-l2)==1)))//注意只能高度减小才能滑落，高度相等是不能滑落的 { q[i].dp=max(q[i].dp,(q[j].dp+1)); mat=max(mat,q[i].dp);//不一定节点大的是最大滑落值，自己想一想就知道了，所以要随时记录当前的最大滑落值。 } } } printf("%d\n",mat); } return 0;}
POJ1088:滑雪（简单dp)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。