hdu|hdu 5256 最少修改多少个数能使原数列严格递增（LIS） hdu5256最少修改多少个数能使原

Problem Description
我们有一个数列A1,A2...An，你现在要求修改数量最少的元素，使得这个数列严格递增。其中无论是修改前还是修改后，每个元素都必须是整数。请输出最少需要修改多少个元素。
Input
第一行输入一个T(1≤T≤10)，表示有多少组数据
每一组数据：
第一行输入一个N(1≤N≤105)，表示数列的长度
【hdu|hdu 5256 最少修改多少个数能使原数列严格递增（LIS）】第二行输入N个数A1,A2,...,An。
每一个数列中的元素都是正整数而且不超过106。
Output
对于每组数据，先输出一行
Case #i:
然后输出最少需要修改多少个元素。
Sample Input
2
2
1 10
3
2 5 4
Sample Output
Case #1:
0
Case #2:
1

文章图片

文章图片

1 # include 2 # include 3 # include 4 # include 5 # include 6 # define LL long long 7 using namespace std ; 8 9 int a[100010] ; 10 int f[100010] ; 11 //int dp[100010] ; 12 int n ; 13 14 int bsearch(int size, const int &a) { 15int l=0, r=size-1; 16while( l <= r ){ 17int mid = (l+r)/2; 18if( a >= f[mid-1] && a < f[mid] ) return mid; // >&&<= 换为: >= && < 19else if( a < f[mid] ) r = mid-1; 20else l = mid+1; 21} 22 } 23 24 int LIS() 25 { 26int i, j, size = 1; 27f[0] = a[0]; 28//dp[0] = 1; 29for( i=1; i < n; ++i ) 30{ 31if( a[i] < f[0] ) j = 0; // <= 换为: < 32else if( a[i] >= f[size-1] ) j = size++; // > 换为: >= 33else j = bsearch(size, a[i]); 34f[j] = a[i]; 35//dp[i] = j+1; 36} 37 38return size; 39 } 40 41 42 int main () 43 { 44// freopen("in.txt","r",stdin) ; 45int T ; 46scanf("%d" , &T) ; 47int Case = 1 ; 48while(T--) 49{ 50 51printf("Case #%d:\n" , Case) ; 52Case++ ; 53scanf("%d" , &n) ; 54int i ; 55for (i = 0 ; i < n ; i++) 56{ 57int x ; 58scanf("%d" , &x) ; 59a[i] = x-i; 60} 61 62printf("%d\n" , n-LIS()) ; 63} 64 65 66return 0 ; 67 }

View Code
转载于:https://www.cnblogs.com/mengchunchen/p/4542659.html