首页 > 代码库 > 建筑群最长坡值

建筑群最长坡值

建筑群最长坡值

时间限制(普通/Java):1000MS/3000MS          运行内存限制:65536KByte
总提交:454            测试通过:168

描述

建筑群所有建筑高度分别为h1h2…hN,可以得到一些单调递减的序列hi1hi2…hiK,其长度称为建筑群的坡值,这里1i1< i2<…< iKN

你的任务:对于给定的建筑群所有建筑高度,求出建筑群最长坡值。

输入

第一行是建筑群中的建筑数N1N1000)。

第二行依次给出各个建筑的高度(大小从01000),中间用空格分开。

输出

建筑群最长坡值

样例输入

10
108 60 79 50 119 40 90 230 20 80

样例输出

5

题目来源

南京邮电大学计算机学院首届ACM程序设计大赛(2009)


分析:Dynamic Programming(动态规划)。

题目的意思是找到一组 个数最多 的 递减数列。只需输出个数。


但是具体怎么规划呢。。。循环的构造很关键,构造n个坡值,最大的即为最长坡值。DP其实很有内涵。

#include<stdio.h>

//建筑群最长坡值
//DP——动态规划

int main()
{
	int n, h[1000];
	int sum[1000]; // 下标为i的最长坡值
	int max;

	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d",&h[i]);

	for(int i=0;i<n;i++)
	{
		sum[i] = 1;
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<i;j++)
		{
			if(h[j] > h[i])
				sum[i] = sum[j]+1>sum[i] ? sum[j]+1 : sum[i];
		}
	}

	max = sum[0];
	for(int i=1;i<n;i++)
	{
		if(sum[i] > max)
			max = sum[i];
	}
	printf("%d\n",max);

	return 0;
}