POJ 3670 , 3671 LIS - c++编程基础

题意：两题意思差不多，都是给你一个序列，然后求最少需要改变多少个数字，使得成为一个最长不升，或者最长不降子序列。

当然3671是只能升序，所以更简单一点。

然后就没有什么了，用二分的方法求LIS即可。

贴一下3670，3671几乎没变化，只需将求最长不升的那部分去掉即可。

#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#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  
#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;  
}