滑雪问题.txt

ACM资料大集合

/*
输入：
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
输出：
25

输入：
5 6
21 19 17 16 15 14
22 24 20 18 12 13
23 25 26 13 11  9
 3  2  1  27 8 10 
 4  5  6  28 7 30
输出：
15 
*/
//滑雪问题 PKU 1088 动态规划
//思路：从最高点开始标路径，如果某点的周围没有比它更高的点，改点为起始点，路径记为1，
//	否则路径记为max+1,max为周围点路径的最大值。
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>

using namespace std;

typedef struct point
{
	int x;
	int y;
	int high;
}point;

point p[10008];
int next[101][101];
int go[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int shuru[101][101];
int re[101][101];
int result[10008];

bool cmp(point a,point b)
{
	return a.high>b.high;
}

void print(int r,int c)
{
	int i,j;
	for(i=0;i<r;i++)
	{
		for(j=0;j<c;j++)
			cout<<re[i][j]<<" ";
		cout<<endl;
	}
	cout<<endl;
	system("pause");
}

int play(int R,int C,int num)
{
	int i,j,max,flag,answer=0;
	point temp;
	sort(p,p+num,cmp);
	for(i=0;i<num;i++)
	{
		flag=0;
		max=0;
		for(j=0;j<4;j++)
		{
			temp.x=p[i].x+go[j][0];
			temp.y=p[i].y+go[j][1];
			temp.high=shuru[temp.y][temp.x]; 
			if(temp.x >=0&&temp.x <C&&temp.y >=0 && temp.y <R)
			{//保证不越界
				if(p[i].high<temp.high)
				{//不是起始点
					flag=1;
					if(max<re[temp.y][temp.x]) max=re[temp.y][temp.x];//求周围路径的最大值
				}
			}
		}
		if(flag==0) {result[i]=1;re[p[i].y][p[i].x]=1;}
		else {result[i]=max+1;re[p[i].y][p[i].x]=max+1;}
		if(answer<result[i]) answer=result[i];//最长路径
	}
	return answer;
}

int main()
{
	int row,cc,i,j,k;
	while(scanf("%d%d",&row,&cc)!=EOF)
	{
	k=0;
	for(i=0;i<row;i++)
	{
		for(j=0;j<cc;j++)
		{
			scanf("%d",&shuru[i][j]);
			p[k].x=j;
			p[k].y=i;
			p[k].high =shuru[i][j];
			k++;
		}
	}
	cout<<play(row,cc,k)<<endl;
	}
	return 0;
}