hdu5256 序列變換 最長遞增子序列
//給一個序列a , 最少改變多少元素使得其變為單調遞增序列
//對於這個序列，更換的最少就是找一個最長的不需要更換的子序列
//所以就是求a[i] - i的最長遞增子序列
#include
#include
#include
#include
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 ;
}
