题意:两题意思差不多,都是给你一个序列,然后求最少需要改变多少个数字,使得成为一个最长不升,或者最长不降子序列。
当然3671是只能升序,所以更简单一点。
然后就没有什么了,用二分的方法求LIS即可。
贴一下3670,3671几乎没变化,只需将求最长不升的那部分去掉即可。
#include <set> #include <map> #include <stack> #include <cmath> #include <queue> #include <cstdio> #include <string> #include <vector> #include <iomanip> #include <cstring> #include <iostream> #include <algorithm> #define Max 2505 #define FI first #define SE second #define ll long long #define PI acos(-1.0) #define inf 0x3fffffff #define LL(x) ( x << 1 ) #define bug puts("here") #define PII pair<int,int> #define RR(x) ( x << 1 | 1 ) #define mp(a,b) make_pair(a,b) #define mem(a,b) memset(a,b,sizeof(a)) #define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i ) using namespace std; int a[33333] ;int n ; int qe[33333] ; int LIS(int *x ){ int head = 0 ;mem(qe ,0) ; for (int i = 0 ; i < n ; i ++ ){ if(head == 0 || x[i] >= qe[head]){ qe[++ head] = x[i] ; } else { int r = head , l = 1 ; while(r >= l){ int mid = l + r >> 1 ; if(qe[mid] <= x[i])l = mid + 1 ; else r = mid - 1 ; } qe[l] = x[i] ; } } return head ; } int main() { cin >> n ; for (int i = 0 ; i < n ; i ++ ){ scanf("%d",&a[i]) ; } int x = LIS(a) ; reverse(a , a + n) ; int y = LIS(a) ; cout << n - max(x , y) << endl; return 0; }