五一到了，PKU-ACM队组织大家去登山观光，队员们发现山上一个有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？
Input
Line 1： N (2 <= N <= 1000) 景点数
Line 2： N个整数，每个景点的海拔
Output
最多能浏览的景点数
Sample Input
8 186 186 150 200 160 130 197 220
Sample Output
4
#include<stdio.h>
int main()
{
int n,h,l,i,k,j,a[1001],max=0;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);//记录海拔
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++) //j点开始下山
{
l=a[i];int s=1;
for(k=i;k<=j;k++)
{
if(a[k]>l){
s++;l=a[k];//上山所看风景数
}
}
for(k=j;k<n;k++){//下山
if(a[k]<l){
s++;l=a[k];
}
}
if(max<s) max=s;//记录最大数
}
}
printf("%d\n",max);
}
你分类写的Ｃ＃但是你的代码是C。到底要用什么语言呢？
不过没关系，算法是一样的。
这是典型的 longest increasing subsequence (LIS) 问题。你可以搜索，有很多现成的解法，比如https://www.geeksforgeeks.org/longest-increasing-subsequence-dp-3/ 。
你的代码最主要的是没有用辅助空间一维数组保存每个山峰的ＬＩＳ值。从而海拔有升有降的时候结果可能不准确。下面得代码调试通过了，供你参考。
#include<stdio.h>
/* lis() returns the length of the longest increasing subsequence in arr[] of size n */
int lis(int arr[], int n)
{
int lis[n];
int max = 1;
int i, j;
/* Compute optimized LIS values in increasing order */
lis[0] = 1;
for (i = 1; i < n; i++) {
lis[i] = 1;
for (j = 0; j < i; j++)
if (arr[i] > arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
}
// Retrieve maximum value in lis[]
for (int i = 1; i < n; i++)
if (lis[i] > max)
max = lis[i];
return max;
}
int main()
{
int n, a[1001], max, i;
scanf("%d", &n);
for(i = 0; i < n; i++)
scanf("%d", &a[i]);//记录海拔
max = lis(a, n);
printf("%d\n",max);
return 0;
}
// Output
About • FAQ • Blog • Terms of Use • Contact Us • GDB Tutorial • Credits • Privacy
© 2016 - 2021 GDB Online
SPONSOR
Mailchimp — Grow sales with our all-in-one Marketing Platform. It’s an easy way to market smarter. Try it for free.
Language
C
main.c
input
186 186 150 200 160 130 197 220
8
186 186 150 200 160 130 197 220
4