OpenJ_Bailian - 2995-登山（两遍最长上升子序列+枚举顶点）-白红宇

OpenJ_Bailian - 2995-登山（两遍最长上升子序列+枚举顶点）

阅读量：5009 次

发布时间：2019-06-12

本文共 2306 字，大约阅读时间需要 7 分钟。

五一到了，PKU-ACM队组织大家去登山观光，队员们发现山上一个有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？

InputLine 1： N (2 <= N <= 1000) 景点数

Line 2： N个整数，每个景点的海拔Output最多能浏览的景点数Sample Input

8186 186 150 200 160 130 197 220

Sample Output

4 代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               const int maxn=1e4+5;typedef long long ll;using namespace std;int a[maxn];int dp1[maxn],dp2[maxn];int main(){ int n; cin>>n; for(int t=1;t<=n;t++) { scanf("%d",&a[t]); } for(int t=1;t<=n;t++) { dp1[t]=1; dp2[t]=1; } for(int t=1;t<=n;t++) { for(int j=1;j
               
                a[j]) dp1[t]=max(dp1[t],dp1[j]+1); } } for(int t=n;t>0;t--) { for(int j=n;j>t;j--) { if(a[t]>a[j]) dp2[t]=max(dp2[t],dp2[j]+1); } } int ans=-1; for(int t=1;t<=n;t++) { ans=max(dp1[t]+dp2[t]-1,ans); } cout<
                
                 <

import java.util.Scanner;public class Main {    public static void main(String[] args) {        // TODO 自动生成的方法存根                int[] a= new int[1005];        int[] b= new int[1005];        int[] dp1=new int[1005];        int[] dp2=new int[1005];         Scanner sc=new Scanner(System.in);        int N=sc.nextInt();        for(int t=1;t<=N;t++)        {           a[t]=sc.nextInt();        }        for(int t=1;t<=N;t++)        {            b[N-t+1]=a[t];        }        for(int t=1;t<=N;t++)        {            dp1[t]=1;            dp2[t]=1;        }        for(int t=1;t<=N;t++)        {            for(int j=1;j
      
       a[j])                {                    dp1[t]=max(dp1[t],dp1[j]+1);                }            }        }        for(int t=1;t<=N;t++)        {                        for(int j=1;j
       
        b[j])                {                    dp2[t]=max(dp2[t],dp2[j]+1);                }            }        }        int ans=0;        for(int t=1;t<=N;t++)        {            ans=max(dp1[t]+dp2[N-t+1]-1,ans);                    }        System.out.println(ans);        sc.close();    }    private static int max(int i, int j) {        // TODO 自动生成的方法存根        if(i>j)        return i;        else        return j;    }}

转载于:https://www.cnblogs.com/Staceyacm/p/11253871.html

你可能感兴趣的文章