【POJ 3903】Stock Exchange
写了发暴力LIS超时了 才知道原来还有二分LIS…………孤陋寡闻了。。。原理很简单 LIS的dp数组必定是递增的 所以暴力的时候改的也只是>x的第一个dp点 所以二分找到这个点改一下就行。。。弱了TOT
代码如下:
#include <iostream>#include <cstdio>using namespace std;int dp[100001];int len;int main(){int n,i,j,a,l,r,mid;dp[0] = -1;while(~scanf(“%d”,&n)){len = 0;for(i = 0; i < n; ++i){scanf(“%d”,&a);if(a > dp[len]) dp[++len] = a;else{l = 0,r = len;while(l <= r){mid = (l+r)>>1;if(dp[mid] >= a) r = mid-1;else l = mid+1;}dp[l] = a;}}printf(“%d\n”,len);}return 0;}
，当我要取的时候，你淘气的躲开了，
