首页 > 代码库 > 算法复习——求最长不下降序列长度(dp算法)

算法复习——求最长不下降序列长度(dp算法)

题目:

题目背景

161114-练习-DAY1-AHSDFZ T2

题目描述

有 N 辆列车,标记为 1,2,3,…,N。它们按照一定的次序进站,站台共有 K 个轨道,轨道遵从先进先出的原则。列车进入站台内的轨道后可以等待任意时间后出站,且所有列车不可后退。现在要使出站的顺序变为 N,N-1,N-2,…,1,询问 K 的最小值是多少。

    技术分享

例如上图中进站的顺序为 1,3,2,4,8,6,9,5,7,则出站的顺序变为 9,8,7,6,5,4,3,2,1。

输入格式

输入共 2 行。
第 1 行包含 1 个正整数 N ,表示 N 辆列车。
第 2 行包含 N 个正整数,为 1 至 N 的一个排列,表示进站次序。

输出格式

输出共 1 行,包含 1 个整数,表示站台内轨道数 K 的最小值。

样例数据 1

输入  [复制]

 

 


1 2 3

输出

3

样例数据 2

输入  [复制]

 

 


1 3 2 4 8 6 9 5 7

输出

5

备注

【数据规模与约定】
对于 30% 的数据,N≤10;
对于 70% 的数据,N≤2000;
对于 100% 的数据,N≤100000。

题解:

  其实就是求最长不下降序列的长度·····

  设 dp[i] 表示处理到当前位置时,之前整数能够构成的长度为 i 的最长不下降序列中,第 i 位上数字最小的值(即系列中最后一位最小),dp[i]用二分查找的方法确定。

  按顺序从左到右,计算每个数字作为最长不下降序列最后一个数字,就能构成的最长序列的长度。

  时间复杂度:O(N*long2n)

心得:

  先开始根据样例模拟的时候可以得出这几组数:1  32 4 865 97····然后分析每组数据的开头的数其实是很好分析的··

代码:

  

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
const int N=100005;
int dp[N],ans=0,n,num;
int main()
{
  //freopen("lic.in","r",stdin);
  scanf("%d",&n);
  for(int i=1;i<=n;i++)
  {
    scanf("%d",&num);
    int left=1,right=ans;
    while(left<=right)
    {
      int mid=(left+right)/2;
      if(num<=dp[mid])
        right=mid-1;
      else
        left=mid+1;
    }
    if(left>ans)  ans++;
    dp[left]=num;
  }
  cout<<ans<<endl;
  return 0;
}

 

算法复习——求最长不下降序列长度(dp算法)