51Nod1134 最长递增子序列（动归）

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

这道题用动归的思想写，在所给的数组中找到最长递增子序列。定义一个新的数组存最长子序列，第i项如果大于数组的最后一项，就加入数组，如果小于，就用二分查找找到第一个大于第i项的数，然后取代之。

lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

具体代码如下：

#include<iostream>
#include<cstring> 
#include<algorithm>
using namespace std;
int dp[50001];
int main()
{
  int n;
  cin>>n;
  int a[50001],i;
  for(i=0;i<n;i++)
    cin>>a[i];
  dp[0]=a[0];
  int len=0;
  for(i=1;i<n;i++)
  {
    if(a[i]>dp[len])
      dp[++len]=a[i];
    else
    {
      int t=lower_bound(dp,dp+len,a[i])-dp; 
//      dp到dp+len容易写错成到dp+len-1
      dp[t]=a[i];
    } 
//    cout<<dp[len]<<endl;  
  }
//  for(i=0;i<=len;i++)
//    cout<<dp[i];
  cout<<len+1<<endl;
  return 0;
 }