Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
LIS+二分 16ms ac 是ac了 可是这题竟然有那么多的0ms 真心膜拜啊 。附代码(仅供参考)// 二分查找时可以直接用upper_bound来找或者自己写个find函数,两个我都试了,时间上几乎没有差别 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define maxn 30008 int data[maxn]; int LIS[maxn], len[maxn], ans; int find( int x ){ int l=1, r=len[0], mid; while(l <= r) { mid = (l+r)>>1; if(len[mid] > x) r=mid-1; else l= mid+1; } return l; }; void get(int *a, int n){ LIS[0]=1, len[1] = a[0]; len[0] = 1; for( int i=1; i<n; ++i ){ if(a[i] >= len[len[0] ] ) { LIS[i] = ++len[0]; len[len[0] ] = a[i]; }else { //int x = upper_bound(len+1, len+1+len[0], a[i])-len; int x = find(a[i]); LIS[i] = x; // cout<<"***" << x << endl; len[LIS[i] ] = a[i]; } if(LIS[i] > ans) ans = LIS[i]; } }; int main( int argc, char** argv ) { int n; while( ~scanf("%d", &n) ) { for(int i=0; i<n; ++i ) scanf("%d", data+i); ans = 1; get(data, n); reverse(data, data+n); get(data, n); printf("%d\n", n-ans); } return (EXIT_SUCCESS); }; Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator