POJ 3670 & 3671：最長不下降子序列 (LNDS) 求最小修改次數

• 若 x ≥ tail[len]：tail[++len] = x
• 否則：二分查找 tail 中 第一個 > x 的位置 pos，tail[pos] = x

最終 len 即為 LNDS 長度。

POJ 3670 代碼（雙向）

#include 
#include 
#include 
using namespace std;
const int MAXN = 30010;
int a[MAXN], tail[MAXN];

int find_pos(int x, int len) { // 找第一個 > x 的位置
    int l=1, r=len, pos=len+1;
    while (l<=r) {
        int mid=(l+r)/2;
        if (tail[mid] > x) { pos=mid; r=mid-1; }
        else l=mid+1;
    }
    return pos;
}

int LNDS(int n) {
    int len=0;
    for (int i=0; i= tail[len]) tail[++len]=a[i];
        else tail[find_pos(a[i], len)] = a[i];
    }
    return len;
}

int main() {
    int n;
    while (scanf("%d", &n)==1) {
        for (int i=0; i

#include 
#include 
#include 
using namespace std;
const int MAXN = 30010;
int tail[MAXN];

int find_pos(int x, int len) { ... } // 同上

int main() {
    int n;
    while (scanf("%d", &n)==1) {
        int len=0, x;
        for (int i=0; i= tail[len]) tail[++len]=x;
            else tail[find_pos(x, len)] = x;
        }
        printf("%d\n", n - len);
    }
    return 0;
}