M_sea

洛谷2501 [HAOI2006]数字序列
LuoguBZOJ分析神仙结论题......不看题解完全不会的说第一问最少改动$\Rightarrow$最多不改动...
扫描右侧二维码阅读全文
30
2019/01

洛谷2501 [HAOI2006]数字序列

Luogu

BZOJ

分析

神仙结论题......

不看题解完全不会的说qwq

第一问

最少改动$\Rightarrow$最多不改动。

设$f[i]$表示前$i$个点最多不改动的个数。

显然有$f[i]=\max\limits_{j=1}^{i-1}\left\{f[j]\right\}+1\quad(a_i-a_j>i-j)$

发现条件不太好处理,改一下,变成$a_i-i>a_j-j$。

然后设$b[i]=a[i]-i$,于是求$b$的最长上升子序列救星了。

第二问

神仙结论is coming

$[l,r]$的最优解一定是$b[l\sim k]$变成$b[l]$,$b[k+1\sim r]$变成$b[r]$。

设$g[i]$表示前$i$个数的最小代价,可以枚举$k$取个$\min$来转移了。

具体的转移要用到前缀和,上界大概是$O(n^3)$的,然而完全跑不满。


细节和具体实现见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

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

const int N=35000+10;
const int INF=0x3f3f3f3f;

struct Edge { int v,nxt; };
Edge e[N];
int head[N],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;
}

int n,top=0;
int a[N],b[N];
int c[N],f[N];
ll g[N],s1[N],s2[N];

int main() {
    n=read();
    for (re int i=1;i<=n;++i) a[i]=read(),b[i]=a[i]-i;
    b[0]=-INF,b[++n]=INF;
    for (re int i=1;i<=n;++i) {
        int L=0,R=top;
        while (L<R) {
            int mid=(L+R+1)>>1;
            if (c[mid]<=b[i]) L=mid;
            else R=mid-1;
        }
        if (L==top) ++top;
        f[i]=L+1,c[L+1]=b[i];
    }
    printf("%d\n",n-f[n]);
    for (re int i=n;i>=0;--i) addEdge(f[i],i);
    memset(g,0x3f,sizeof(g)); g[0]=0;
    for (re int i=1;i<=n;++i)
        for (re int j=head[f[i]-1];j;j=e[j].nxt) {
            int v=e[j].v;
            if (v>i) break; if (b[v]>b[i]) continue;
            for (re int k=v;k<=i;++k)
                s1[k]=abs(b[k]-b[v]),s2[k]=abs(b[k]-b[i]);
            for (re int k=v+1;k<=i;++k)
                s1[k]+=s1[k-1],s2[k]+=s2[k-1];
            for (re int k=v;k<i;++k)
                g[i]=min(g[i],g[v]+s1[k]-s1[v]+s2[i]-s2[k]);
        }
    printf("%lld\n",g[n]);
    return 0;
}
最后修改:2019 年 05 月 26 日 08 : 10 PM

1 条评论

  1. smy

    怎么能发表情呢qwq

发表评论