登山 //为什么交上去后错的？

Question

五一到了，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);
}

Answer 1

你分类写的Ｃ＃但是你的代码是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