【HDU】5256 系列转换（上涨时间最长的序列修饰）

假设a[i]和a[j]我想的一样，满足条件的需要是

a[j] - a[i] > j - i

也就是说，a[i] - i < a[j] - j

例1 4 2 不满意，所以1和2必须有必要之间改变

a[i] - i求其最长上升子序列就能够了

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 100005;
const int  INF = 5000000;
int n;
int arr[maxn],g[maxn];
int main(){
    int T,Case = 1;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i = 1; i <= n; i ++) g[i] = INF;
        for(int i = 1; i <= n; i++){
            scanf("%d",&arr[i]);
            arr[i] -= i;
        }
        int ans = 0;
        for(int i = 1; i <= n; i++){
            int pos = upper_bound(g + 1,g + n + 1,arr[i]) - g;
            ans = max(ans,pos);
            g[pos] = arr[i];
        }
        printf("Case #%d:
",Case++);
        printf("%d
",n - ans);
    }
    return 0;
}