洛谷P1020 导弹拦截

洛谷P1020

O(logN)做法:
dp1[i]:=长度为i的非升子序列中末尾元素的最大值
dp2[i]:=长度为i的上升子序列中末尾元素的最小值

注意
dp1中元素可以相等,用upper_bound搜索替换位置.
dp2中元素不可以相等,用lower_bound搜索替换位置.

可参考<<挑战程序设计竞赛>>P65

code:

#include <time.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

#define maxn 0x3f3f3f3f
#define lowbit(x) (x & -x)
typedef long long ll;
typedef unsigned long long ull;

int t[100005];
int dp1[100005];
int dp2[100005];
int ans1, ans2;
int main() {
  // clock_t start,end;
  // start=clock();
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);

  int n = 0;
  while (cin >> t[++n]);
  n--;
 /* O(n^2) 
  for (int j = 1; j <= i; ++j) {
    for (int k = 0; k < j; ++k) {
      if (t[k] >= t[j] || k == 0) dp1[j] = max(dp1[j], dp1[k] + 1);
      if (t[k] < t[j]) dp2[j] = max(dp2[k] + 1, dp2[j]);
      ans1 = max(dp1[j], ans1);
      ans2 = max(dp2[j], ans2);
    }
  }
  cout << ans1 << endl;
  cout << ans2 << endl;
 */

 //O(logN)
 for(int i=1;i<=n;++i){
     dp2[i]=maxn;
 }
  for(int i=1;i<=n;++i){
      *upper_bound(dp1+1,dp1+n+1,t[i],greater<int>())=t[i];
      *lower_bound(dp2+1,dp2+n+1,t[i])=t[i];
  }
  ans1=lower_bound(dp1+1,dp1+n+1,0,greater<int>() )-(dp1+1);
  ans2=lower_bound(dp2+1,dp2+n+1,maxn)-(dp2+1);
  cout<<ans1<<endl;
  cout<<ans2<<endl;
  // end=clock();
  // cout<<"TIME PASSED:"<<end-start<<endl;
  return 0;
}