【bzoj1049】【待续】[HAOI2006]数字序列

2015.05.25 16:07 Mon | 9次阅读 | 旧日oi | 固定链接 | 源码

Description

现在我们有一个长度为n的整数序列A。但是它太不好看了,于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数,也不希望改变的幅度太大。
n<=35000
题解
第一问的话把每个a[i]减去i然后求最长不下降子序列nlogn
第二问的话比较难搞,我们把dp值一样的位置按从后往前的顺序加进邻接表,然后令f[i]表示前i个数,i不移动位置,变成符合题意的序列的最小更改值。
则有f[i]=f[j]+change(j+1,i),其中j满足dp[j]=dp[i]-1,change(j+1,i)这部分我们可以发现,一定是从某个j<=k<=i的k开始,k之前的变成a[j],k之后的变成a[i],就这样维护两个前缀和就可以了,理论复杂度n^2,实际复杂度可A。
但是把inf设为0x3f3f3f3f3f3f3f3fll和0x3f3f3f3f到底tm有什么区别,为什么前面的交上去就wa……

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define N 55555
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;
int n,cnt;
ll a[N],dp[N],f[N],l[N],sum1[N],sum2[N];
struct edge{
    int to,next;
}e[N];
int h[N],tp;
void ae(int u,int v)
{
    e[tp].to=v;
    e[tp].next=h[u];
    h[u]=tp++;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        a[i]-=i;
    }
    n++;
    a[n]=inf; a[0]=-a[n];
    for(int i=0;i<=n;i++) l[i]=inf;
    cnt=1; l[1]=a[1]; l[0]=-l[0];
    dp[0]=0; dp[1]=1;
    for(int i=2;i<=n;i++)
    {
        int x=upper_bound(l,l+1+cnt,a[i])-l;
        cnt=max(cnt,x);
        l[x]=min(l[x],a[i]);
        dp[i]=x;
    }
    cout<<n-dp[n]<<endl;
    memset(h,-1,sizeof h); 
    for(int i=n;i>=0;i--) ae(dp[i],i),f[i]=inf;
    f[0]=0;
    for(int i=1;i<=n;i++)
    for(int v,j=h[dp[i]-1];j!=-1;j=e[j].next)
    {
        v=e[j].to;
        if(v>i) break;
        if(a[v]>a[i]) continue;
        for(int k=v;k<=i;k++) sum1[k]=abs(a[k]-a[v]),sum2[k]=abs(a[k]-a[i]);
        for(int k=v+1;k<=i;k++) sum1[k]+=sum1[k-1],sum2[k]+=sum2[k-1];
        for(int k=v;k<i;k++)
            f[i]=min(f[i],f[v]+sum1[k]-sum1[v]+sum2[i]-sum2[k]);
    }
    cout<<f[n]<<endl;
}```