删区间

题意：

给出一个长度为的数组，你每次需要选出一个长度大于1的区间[, ]并删掉它，代价

是左右端点的元素之差的绝对值| − |，之后再将左右两个数组接起来构成一个新的数组。

你的任务是要求出删除整个数组的最小代价和。

题解：

40pts

暴力区间 dp

70pts：

设 \(f[i]\) 表示删完 \(1-i\) 这段区间的最小代价

转移时枚举这次删去的区间的左端点，在取个 \(min\) 就可以.

具体方程长这样

f[i] = min(f[i], f[j-1] + abs(a[i]-a[j])

100pts

观察一下上面的转移柿子，发现是不可以用单调队列优化的，一个取绝对值就很难处理。

当时考试的时候我就卡在这里没想出来，然后就暴力滚粗了。

实际上，我们的转移柿子可以写成这样：

[] = [ − 1] − + , ≤
f[i] = [ − 1] + − , >

可以维护两棵权值线段树，一个维护最小值 \(f[j-1] - a[j]\) 一个维护 \(f[j-1] + a[j]\)

在 \(1-Ai\) 区间里取最小值 \(f[j-1] - a[j]\) 在 \(Ai - \infty\) 区间里取最小值 \(f[j-1] + a[j]\)

最后不要忘记把权值离散化；

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

#define int long long

const int N = 5e5+10;

const int inf = 1e13;

int n,tot,f[N],a[N],h[N],rk[N],tr[N<<2][2];

inline int read()

{

    int s = 0, w = 1; char ch = getchar();

    while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}

    while(ch >= '0' && ch <= '9'){s =s * 10+ch - '0'; ch = getchar();}

    return s * w;

}

void up(int now,int o)

{

    tr[o][now] = min(tr[o<<1][now],tr[o<<1|1][now]);

}

void build(int now,int o,int L,int R)

{

    tr[o][now] = inf;

    if(L == R)

    {

        tr[o][now] = inf;

        return;

    }

    int mid = (L + R)>>1;

    build(now,o<<1,L,mid);

    build(now,o<<1|1,mid+1,R);

}

void chenge(int now,int o,int L,int R,int x,int val)

{

    if(L == R)

    {

        tr[o][now] = min(tr[o][now],val);

        return;

    }

    int mid = (L + R)>>1;

    if(x <= mid) chenge(now,o<<1,L,mid,x,val);

    if(x > mid) chenge(now,o<<1|1,mid+1,R,x,val);

    tr[o][now] = min(tr[o<<1][now],tr[o<<1|1][now]);

}

int query(int now,int o,int L,int R,int l,int r)

{

    int res = inf;

    if(l <= L && r >= R) return tr[o][now];

    int mid = (L + R)>>1;

    if(l <= mid) res = min(res,query(now,o<<1,L,mid,l,r));

    if(r > mid) res = min(res,query(now,o<<1|1,mid+1,R,l,r));

    return res;

}

signed main()

{

//  freopen("remove.in","r",stdin);

//  freopen("remove.out","w",stdout);

    n = read();

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

    {

        a[i] = h[i] = read();

    }

    sort(a+1,a+n+1);

    tot = unique(a+1,a+n+1)-a-1;

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

    {

        rk[i] = lower_bound(a+1,a+tot+1,h[i])-a;

    }

    build(0,1,1,tot); build(1,1,1,tot);

    f[1] = inf;

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

    {

        chenge(0,1,1,tot,rk[i-1],f[i-2] - h[i-1]);

        chenge(1,1,1,tot,rk[i-1],f[i-2] + h[i-1]);

        int t1 = query(0,1,1,tot,1,rk[i]) + h[i];

        int t2 = query(1,1,1,tot,rk[i],tot) - h[i];

        f[i] = min(t1,t2);

    }

    printf("%lld\n",f[n]);

    fclose(stdin); fclose(stdout);

    return 0;

}