首页 > 代码库 > BZOJ 1049 数字序列（LIS）

BZOJ 1049 数字序列（LIS）

2024-07-08 23:41:35   223人阅读

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1049

题意：给出一个数列A，要求：（1）修改最少的数字使得数列严格递增；（2）在（1）的基础上使得修改的绝对值之和最小。

思路：对于第一问看起来像是求最长上升子 列，其实不是。我们想，若对于i<j，j能由i转移过来，那么需满足A[j]-A[i]>=j-i才行，这样我们发现只要A[j]-j& gt;=A[i]-i即可。因此令A[i]=A[i]-i，这样求LIS即可。对于第二问，若i<j且j由i转移过来，那么[i+1,j-1]之间 的数字或者大于A[j]或者小于A[i]，最后这段区间的数字必然是前面一段修改为A[i]后面一段修改为A[j]。因此，记录每个位置j由哪些前面的位 置转移过来，直接暴力枚举前面的位置i即可。然后对于[i+1,j-1]，暴力枚举中间的分界点。

 

int a[N],b[N],c[N],n,f[N];vector<int> V[N];int S[N],M;int find(int x){    int low=1,high=M,mid;    while(low<=high)    {        mid=(low+high)>>1;        if(b[mid]==x) return mid;        if(b[mid]<x) low=mid+1;        else high=mid-1;    }}void add(int x,int y){    while(x<=n) upMax(S[x],y),x+=x&-x;}int get(int x){    int ans=0;    while(x) upMax(ans,S[x]),x-=x&-x;    return ans;}int Ans;void deal1(){    int i;    a[++n]=INF;    FOR1(i,n) b[i]=a[i];    sort(b+1,b+n+1);    M=unique(b+1,b+n+1)-(b+1);    FOR1(i,n) c[i]=find(a[i]);    Ans=0;    FOR1(i,n)     {        f[i]=get(c[i])+1;        add(c[i],f[i]);        upMax(Ans,f[i]);    }    PR(n-Ans);}i64 sum1[N],sum2[N],dp[N];void deal2(){    int i,j,k,t;    V[0].pb(0);    FOR1(i,n) V[f[i]].pb(i),dp[i]=inf;    a[0]=-INF; dp[0]=0;    FOR1(i,n)     {        FOR0(j,SZ(V[f[i]-1]))        {            k=V[f[i]-1][j];            if(k>i) break;            if(a[k]>a[i]) continue;            for(t=k;t<=i;t++) sum1[t]=abs(a[t]-a[k]),sum2[t]=abs(a[t]-a[i]);            for(t=k+1;t<=i;t++) sum1[t]+=sum1[t-1],sum2[t]+=sum2[t-1];            for(t=k;t<i;t++) upMin(dp[i],dp[k]+sum1[t]+sum2[i]-sum2[t]);        }    }    PR(dp[n]);}int main(){    RD(n);    int i;    FOR1(i,n) RD(a[i]),a[i]-=i;    deal1(); deal2();}

 

 

 


联系
我们