数字滑雪

10349 数字滑雪
时间限制:1000MS 内存限制:65535K 提交次数:0 通过次数:0
语言: not limited
描述
你喜欢滑雪吗？肯定有许多人喜欢，因为滑雪的确刺激！
可是为了获得速度，滑的区域必须向低处倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。
现在的问题是：给定区域中各点的高度，想知道这个区域中最长的滑雪坡道长度。
区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：
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更长，事实上，这是最长的一条。
输入格式
输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。
输出格式
13
输出最长滑雪坡道的长度。
输入样例
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
Hint
动规算法思路:
f矩阵与原高度矩阵一样大小，f(i,j)表示从(i,j)位置开始滑，可以获得的最大滑道的长度。
算法步骤：
（1）将高度矩阵从低到高排序；
（2）按滑点从低到高依次计算最长滑道的长度，存于f(i,j)。

（3）f(i,j)中的最大值即原题所求。

-----------------------------------------------------------

10349数字滑雪（动态规划）

#include<stdio.h>

#include"malloc.h"

intmax(int*length,intLlength)//测试正确

{

intmax=0,i;

for(i=0;i<Llength;i++)

if(max<length[i])max=length[i];

returnmax;

}

int**sort(int**adr,intm,intn)//测试正确

{

inti,j,*temp;

for(i=1;i<m*n;i++)

{

for(j=0;j<i;j++)

if(*adr[i]<*adr[j])

{

temp=adr[j];adr[j]=adr[i];adr[i]=temp;

}

}

returnadr;

}

intjudgeLR(int*p,int*q,intm,intn)//判断是否有左右

{

inti;

for(i=0;i<m;i++)

{

if(p==q+i*n)return1;//无左

if(p==q+n-1+i*n)return2;//无右

}

return0;

}

intjudgeTD(int*p,int*q,intm,intn)//测试正确

{

inti;

for(i=0;i<n;i++)

{

if(p==q+i)return3;//无上

if(p==q+(m-1)*n+i)return4;//无下

}

return0;

}

intmain()

{ int**adr;

intm,n,i,j,flagLR,flagTD,Maxlength;

int*high,*length;

scanf("%d%d",&m,&n);

high=(int*)malloc(m*n*sizeof(int));

length=(int*)malloc(m*n*sizeof(int));//无法定义动态二维数组

adr=(int**)malloc(m*n*sizeof(int*));

for(i=0;i<m*n;i++)

adr[i]=(int*)malloc(m*n*sizeof(int));//定义数组存储地址

for(i=0;i<m;i++)

for(j=0;j<n;j++)

{

scanf("%d",&high[i*n+j]);

adr[i*n+j]=&high[i*n+j];

length[i*n+j]=0;//长度初始化

}

adr=sort(adr,m,n);

for(i=m*n-1;i>=0;i--)

{

flagLR=judgeLR(adr[i],high,m,n);

flagTD=judgeTD(adr[i],high,m,n);

if(flagLR!=1)

{

if((*adr[i]<*(adr[i]-1))&&(length[adr[i]-high]<=length[adr[i]-high-1]))

length[adr[i]-high]=length[adr[i]-high-1]+1;

}

if(flagLR!=2)

{

if((*adr[i]<*(adr[i]+1))&&(length[adr[i]-high]<=length[adr[i]-high+1]))

length[adr[i]-high]=length[adr[i]-high+1]+1;

}

if(flagTD!=3)

{

if((*adr[i]<*(adr[i]-n))&&(length[adr[i]-high]<=length[adr[i]-high-n]))

length[adr[i]-high]=length[adr[i]-high-n]+1;

}

if(flagTD!=4)

{

if((*adr[i]<*(adr[i]+n))&&(length[adr[i]-high]<=length[adr[i]-high+n]))

length[adr[i]-high]=length[adr[i]-high+n]+1;

}

}

Maxlength=max(length,m*n);

printf("%d\n",Maxlength+1);

return0;

}����