程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> hdu5256 序列變換 最長遞增子序列

hdu5256 序列變換 最長遞增子序列

編輯:關於C++
//給一個序列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 ;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved