题意:要使序列形成非递减的序列,最少改变几个数;
思路:ans=n-lis();
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<vector> #include<cmath> using namespace std; int n; int cow[30010]; vector<int> len; //len[k]=t,表示k长度的序列的最小末尾值,此数组线性递增。 int binsearch(int val) { int le=0,ri=len.size()-1; while(le<=ri) { int mid=(le+ri)>>1; if(len[mid]<=val) le=mid+1; //注意是<=,因为要求序列非递减! else ri=mid-1; } return le; //返回的第一个k,len[k-1]<=val } int main() { while(scanf("%d",&n)!=EOF) { int c,k; for(int i=0;i<n;i++) { scanf("%d",&c); k=binsearch(c); if(len.size()<=k) len.push_back(c); else len[k]=c; } printf("%d\n",n-len.size()); } return 0; }
POJ 3671 (n log n,LIS),布布扣,bubuko.com
原文:http://blog.csdn.net/code_or_code/article/details/38586865