//给一个序列a , 最少改变多少元素使得其变为单调递增序列
//对于这个序列，更换的最少就是找一个最长的不需要更换的子序列
//所以就是求a[i] - i的最长递增子序列
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std ;
const int maxn = 100010 ;
int b[maxn] ;
int find(int l , int r , int num)
{
while(l<=r)
{
int mid = (l+r) >> 1 ;
if(b[mid] <= num)
l = mid + 1 ;
else
r = mid - 1;
}
return l ;
}
int main()
{
int T ;
int n ;
int a ;
scanf("%d" , &T) ;
int cas = 0 ;
while(T--)
{
scanf("%d" , &n);
int len = 0;
for(int i = 1;i <= n;i++)
{
scanf("%d" , &a) ;
if(i == 1)
{
b[++len] = a - i ;
continue ;
}
int pos = find(1 , len , a - i) ;
b[pos] = a - i ;
if(pos > len)len++ ;
}
printf("Case #%d:\n" , ++cas) ;
printf("%d\n" , n - len) ;
}
return 0 ;
}
hdu5256 序列变换 最长递增子序列
原文：http://blog.csdn.net/cq_pf/article/details/46314885
