POJ 3670 Eating Together (DP，LIS)

题意：给定 n 个数，让你修改最少的数，使得它变成一个不下降或者不上升序列。

析：这个就是一个LIS，但是当时并没有看出来。。。只要求出最长LIS的长度，用总数减去就是答案。

代码如下：

#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
using namespace std ;

typedef long long LL;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const double inf = 0x3f3f3f3f3f3f3f;
const double eps = 1e-8;
const int maxn = 3e4 + 5;
const int dr[] = {0, 0, -1, 1};
const int dc[] = {-1, 1, 0, 0};
int m, n;
inline bool is_in(int r, int c){
    return r >= 0 && r < n && c >= 0 && c < m;
}
int a[maxn], b[maxn];

int solve(){
    fill(b, b+n, INF);
    for(int i = 0; i < n; ++i)
        *upper_bound(b, b+n, a[i]) = a[i];
    return lower_bound(b, b+n, INF) - b;
}

int main(){
    while(scanf("%d", &n) == 1){
        for(int i = 0; i < n; ++i)  scanf("%d", &a[i]);
        int ans = n - solve();
        reverse(a, a+n);
        ans = min(ans, n-solve());
        printf("%d
", ans);
    }
    return 0;
}