主题链接：

HDU5236

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define MAXN 0x3f3f3f3f

using namespace std;

int main()

{

#ifndef ONLINE_JUDGE

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

#endif // ONLINE_JUDGE

    int n,T;

    int v[100050];

    int s[100050];

    scanf("%d",&T);

    for(int Case=1;Case<=T;Case++)

    {

        scanf("%d",&n);

        for(int i=1;i<=n;i++)

        {

            scanf("%d",&v[i]);

            v[i]-=i;

            s[i]=MAXN;

        }

        int maxx=0;

        for(int i=1;i<=n;i++)

        {

            int loc=upper_bound(s+1,s+1+n,v[i])-s;  //找下标1開始第一个比v[i]大的数

            s[loc]=v[i];

            if(loc>maxx)

                maxx=loc;

//            for(int i=1;i<=maxx;i++)

//                cout<<s[i]<<" ";

//            cout<<endl;

//            1 3 2 6 5

//            1 3 2 4 5

        }

        printf("Case #%d:\n%d\n",Case,n-maxx);

    }

    return 0;

}