首页 > 代码库 > 建筑群最长坡值
建筑群最长坡值
建筑群最长坡值
时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte
总提交:454 测试通过:168
总提交:454 测试通过:168
描述
建筑群所有建筑高度分别为h1、h2…hN,可以得到一些单调递减的序列hi1、hi2…hiK,其长度称为建筑群的坡值,这里1≤i1< i2<…< iK≤N。
你的任务:对于给定的建筑群所有建筑高度,求出建筑群最长坡值。
输入
第一行是建筑群中的建筑数N(1≤N≤1000)。
第二行依次给出各个建筑的高度(大小从0到1000),中间用空格分开。
输出
建筑群最长坡值
样例输入
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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。