序列变换(HDU-5256)【LIS】

题目链接：https://vjudge.net/problem/HDU-5256

题意：给一个数列，每一个数都不相同且为整数，现求，最少需要修改多少次才能使该数列为严格上升的。

思路：首先，对于一个严格上升的整数数列a，一定有a[i]>=a[i-1]+1,所以，a[i]-i>=a[i-1]-(i-1),以此为线索，我们生成一个新数列b[i]=a[i]-i,则b[i]>=b[i-1],换句话说，a数列严格递增，等价于b数列不下降，因此，n-b的最长上升子序列长度即为最小修改次数。

代码如下：

 #include<cstdio>

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 using namespace std;

 const int max_v=;

 const int INF=;

 int dp[max_v],n,a[max_v];

 int solve(){

     memset(dp,0x3f,sizeof(dp));

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

         *upper_bound(dp,dp+n,a[i])=a[i];

     return (lower_bound(dp,dp+n,0x3f3f3f)-dp);

 }

 int main(){

     int t;

     scanf("%d",&t);

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

         scanf("%d",&n);

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

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

             a[i-]=a[i-]-i+;

         }

         printf("Case #%d:\n%d\n",i,n-solve());

     }

     return ;

 }

巴特西

序列变换(HDU-5256)【LIS】

最新文章

热门文章