HDU 5256 - 序列变换，树状数组+离散化，二分法

Problem Description

我们有一个数列A1,A2...An，你现在要求修改数量最少的元素，使得这个数列严格递增。其中无论是修改前还是修改后，每个元素都必须是整数。
请输出最少需要修改多少个元素。

Input

第一行输入一个T(1≤T≤10)，表示有多少组数据

每一组数据：

第一行输入一个N(1≤N≤105)，表示数列的长度

第二行输入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

解题思路：

　　不难理解，求 a[i]-i 的最长非递减子序列长度 len ，然后 n-len 就是答案了；

　　以下有两份代码；

　　代码一：

　　　　二分法，打模板即可；时间复杂度O(nlog(n))

　　代码二：

　　　　树状数组，前缀最大值的应用。时间复杂度也是 O(nlog(n))

　　　　回想求LIS的动态规划过程 dp[i]=max(dp[j]); (i>j&&h[j]<h[i])

　　　　利用树状数组的性质： dp[i]=query(a[i]);

　　　　但这道题上还有很多问题，比如负数的存在，应此需要离散化；

　　　　应注意离散化后再去标记最大值，WA了好久好久.. 　　　　

 #include <cstdio>

 #include <cstring>

 using namespace std;

 int c[],n,t,len,a;

 int find(int l,int r,int num){

     while(l<=r){ int mid=(l+r)>>; if(c[mid]<=num) l=mid+; else r=mid-; }

     return l;

 }

 int main(){

     scanf("%d",&t);

     for(int k=;k<=t;k++){

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

         scanf("%d",&n);

         len=; memset(c,,sizeof(c));

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

             scanf("%d",&a);

             if(i==){ c[len]=a-i; continue;    }

             int pos=find(,len,a-i);

             c[pos]=a-i;

             if(len<pos) len=pos;

         }    printf("%d\n",n-len);

     } return ;

 }

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 using namespace std;

 #define N 1000000+5

 int c[N],a[N],b[N],n,t,nmax;

 void modify(int x,int num){while(x<=nmax)c[x]=max(c[x],num),x+=x&-x;}

 int query(int x){int s=;while(x>)s=max(c[x],s),x-=x&-x;return s;}

 int main(){

     scanf("%d",&t);

     for(int k=;k<=t;k++){

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

         scanf("%d",&n);

         memset(c,,sizeof(c)); nmax=;

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

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

             a[i]-=i; b[i]=a[i];

         }

         sort(b,b+n);

         int size=unique(b,b+n)-b;//离散化

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

             a[i]=lower_bound(b,b+size,a[i])-b+;

             nmax=max(a[i],nmax);//离散化以后再去标记最大值

         }

         for(int i=;i<n;i++)modify(a[i],query(a[i])+);//前缀最大值+1

         printf("%d\n",n-query(nmax));

     } return ;

 }

巴特西

HDU 5256 - 序列变换，树状数组+离散化，二分法

最新文章

热门文章

巴特西

HDU 5256 - 序列变换 ，树状数组+离散化 ，二分法

最新文章

热门文章

HDU 5256 - 序列变换，树状数组+离散化，二分法