hdu 5256 序列变换 求最少改变次数使序列变为递增 最长不下降子序列

题意：我们有一个数列A1,A2…An，你现在要求修改数量最少的元素，使得这个数列严格递增。其中无论是修改前还是修改后，每个元素都必须是整数。
请输出最少需要修改多少个元素。

对于任意两个数$A[i]$,$A[j]$($i>j$) 如果满足$A[i]-A[j] \geq i-j$可以使得$[i,j]$区间内的数都是可修改为递增的，可以将上面那个式子转换为$A[i]-i \geq A[j]-j$，这样子，我们可以先求出新的数字$A[i]-i$的最长的不需要改变的长度，也就是最长不下降子序列，这个序列中的数不需要改变，答案为n-最长不下降子序列长度

//author: CHC
//First Edit Time:	2015-09-05 12:55
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=1e+5 + 1000;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
int s[MAXN],A[MAXN],C[MAXN],n;
int main()
{
    int t,cas=0;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&A[i]);
            s[i]=A[i]-i;
        }
        int k=0;
        C[k++]=s[1];
        for(int i=2;i<=n;i++){
            if(C[k-1]<=s[i])C[k++]=s[i];
            else {
                int pos=upper_bound(C,C+k,s[i])-C;
                C[pos]=s[i];
            }
        }
        printf("Case #%d:\n%d\n",++cas,n-k);
    }
    return 0;
}