本文主要是介绍建筑群最长坡值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目的链接为：http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1031
题目的内容为：
描述
建筑群所有建筑高度分别为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
一看就可以知道，本题为典型的动态规划题目。对于动态规划题目，第一步就是搜寻原问题的子问题。
另f[i]为到下标为i时的最长坡长，那么
f[i]=max{f[k](1<=k<=i-1)}+1，其中k满足input[i]<input[k]
代码如下：
#include<iostream>
#define MAXNUM 1001
using namespace std;
int main()
{
int f[MAXNUM],input[MAXNUM];
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>input[i];
}
for(int i=1;i<=n;i++)
{
f[i]=1;//f[i]为到达下标i时的最大坡长
}
for(int i=2;i<=n;i++)
{
for(int k=1;k<i;k++)
{
if(input[i]<input[k])
{
f[i]=f[k]+1>f[i]?f[k]+1:f[i];
}
}
}
int maxnum=f[1];
for(int i=2;i<=n;i++)
{
if(f[i]>maxnum)
{
maxnum=f[i];
}
}
cout<<maxnum<<endl;
system("pause");
return 0;
}
这篇关于建筑群最长坡值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
