洛谷2501 [HAOI2006]数字序列

题解 动态规划 动态规划-线性DP 省选/NOI-
题目链接 编辑文章

题意

有一个序列,要求修改尽可能少的数,使得这个序列变成单调上升序列。输出最少需要修改多少个数,以及在修改最少的前提下,每个数改变的绝对值之和的最小值。

序列长度 $N\le 35000$ 。

题解

子问题1

如果只是单调不降就很简单,但这题要求单调上升。

假设可以保留 $S_i,S_j \ (i < j)$ ,则需要满足 $S_j - S_i \geq j-i$ ,即 $S_j - j\geq S_i-i$ 。

令新序列 $F_i = S_i - i$ ,那么单调不降的部分就可以保留。答案即为 $N -$ 最长不降序列长度。

子问题2

还是假设保留 $F_i,F_j$ ,这时需要将 $[i+1,j-1]$ 的数改成单调不降的。

可以证明最优解一定是找到一个位置 $k$ ,把 $[i,k]$ 的数都变成 $F_i$ ;$[k+1,j]$ 的数都变成 $F_j$ 。

设以 $i$ 结尾的最长不降子序列长度为 $mx[i]$ 。如果确定了 $F_j$ ,那么 $F_i$ 一定满足

$$\begin{cases} i < j \\ F_i \le F_j \\ mx[i]+1=mx[j]\end{cases}$$

对于满足条件的关系 $(i,j)$ 可以在解决子问题1时连边 $mx[i]\rightarrow i$ ,然后遍历所有以 $mx[j]-1$ 为起点的边,再判断是否满足前两个条件即可。

因为所有的最大值也需要被处理,所以令 $F_{N+1}=\inf$ ,然后把序列看成 $N+1$ 个数。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

struct Edge {
    int next,to;
} edge[35005];
long long f[35005],l[35005],r[35005];
int cnt,head[35005],n,s[35005],mx[35005];

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

signed main()
{
    n=read();
    for (int i=1;i<=n;i++) s[i]=read()-i;
    s[++n]=1e9; s[0]=-1e9;
    int len=0;
    add(0,0); add(1,1);
    f[mx[1]=++len]=s[1];
    for (int i=2;i<=n;i++)
    {
        if (s[i]>=f[len]) f[mx[i]=++len]=s[i];
        else
        {
            int p=upper_bound(f+1,f+len+1,s[i])-f;
            f[mx[i]=p]=s[i];
        }
        add(mx[i],i);
    }
    printf("%d\n",n-len);
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for (int x=1;x<=n;x++)
    {
        for (int i=head[mx[x]-1];i;i=edge[i].next)
        {
            int y=edge[i].to;
            if (y>x || s[y]>s[x]) continue;
            l[y]=0;
            for (int j=y+1;j<=x;j++) l[j]=l[j-1]+abs(s[j]-s[y]); //前缀和
            r[x]=0;
            for (int j=x-1;j>=y;j--) r[j]=r[j+1]+abs(s[j]-s[x]); //后缀和
            for (int j=y;j<x;j++) f[x]=min(f[x],f[y]+l[j]+r[j+1]);
        }
    }
    printf("%lld",f[n]);
    system("pause");
    return 0;
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空