前言

有一类 DP 的转移是带有数据结构特征的,针对这一点,我们可以使用合适的数据结构来优化转移。
可能这么干说着不好理解,下面会给出两道题目来详细说明。

例子

1.【arc073f】Many Moves

题目大意:
你有两个整数 a 和 b。
现在 n 个操作,依次执行,每次给你 xi,你选择一个整数 y 变成 xi,代价为|xi-y|。
求做完所有操作的最小代价。
n 1e5,xi 1e9。

先写出 DP 状态,然后来一步一步优化它。
令 $f[i][j][k]$表示,当前到了第 i 步,一个整数为 $x_j$,另一个整数为 $x_k$的最小代价。
然后你发现当完成第 i 步时,一定有一个数是 $x_i$,那么,我们可以把状态优化一下:
令 $f[i][j]$表示,当前到了第 i 步,一个整数为 $x_i$,另一个整数为 $x_j$的最小代价。
把转移方程写出来:
$$
f[i+1][j]=f[i][j]+abs(x_{i+1}-x_{i}) \quad (j<i)\\
f[i+1][i]=min_{j<i}(f[i][j]+abs(x_{i+1}-x_{j}))
$$
在 i 相同时,第一个转移就是区间加,而第二个转移就是全局最小值之后单点赋值,这显然可以用线段树操作,复杂度 $\Theta (nlog_{2}n)$。

2.「HB 省队互测 2019 Round1 Day1」轮回

题目链接
其实这题最难想的是 DP 的状态吧。
考虑,最后的结果一定是,有些动了,有一些没有动。而每一次的移动是任意插入的,那么,在排好 1 到 i-1 之后,如果我们知道最大的没有动的数,是不是说 i 的移动方向就确定了 (就是移到最大的没有动的数的后面)?而这么设计状态是没有后效性的,于是有了这样一个想法:
令 $f[i][j]$表示将序列中的元素 $[1,i]$排好序,且最大的没有被移动的数是 j 的最小时间。
转移:
$$
f[i][j]=min_{pos_{j}<pos_{i}}(f[i-1][j]+b)\\
f[i][j]=min_{pos_{j}>pos_{i}}(f[i-1][j]+a)\\
f[i][i]=min_{pos_{j}<pos_{i}}(f[i-1][j])
$$
这里有一个技巧,因为转移的时候讨论的是 pos 的大小关系,所以为了方便区间操作,我们在实际使用线段树时的下标 j 实际上表示的是 pos 为 j 的值,然后每次转移就是前缀最小值,单点插入,然后前缀加,后缀加。
好像有点难理解,正好这道题是我为数不多的认真写了的题目 (平常都是口胡),放一波代码。(请原谅本人丑陋的码风)

#include<iostream>
#include<cstdio>
#define MAXN 1000001
#define inf 10000000000000
#define ll long long
using namespace std;
unsigned ll n,m,a[MAXN],ans[MAXN<<2],tag[MAXN<<2];
ll A,B;
#define ls(x) x<<1
#define rs(x) x<<1|1
void scan() {
    cin>>n>>A>>B;
    for(int i=1; i<=n; i++) {
        int x;
        scanf("%d",&x);
        a[x]=i+1;
    }
}
inline void push_up(ll p) {
    ans[p]=min(ans[ls(p)],ans[rs(p)]);
}
void build(ll p,ll l,ll r) {
    if(l==r) {
        ans[p]=inf;
        tag[p]=0;
        return;
    }
    ll mid=(l+r)>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
    return;
}
inline void f(ll p,ll l,ll r,ll k) {
    tag[p]=tag[p]+k;
    ans[p]=ans[p]+k;
}
inline void push_down(ll p,ll l,ll r) {
    ll mid=(l+r)>>1;
    f(ls(p),l,mid,tag[p]);
    f(rs(p),mid+1,r,tag[p]);
    tag[p]=0;
}
inline void update(ll nl,ll nr,ll l,ll r,ll p,ll k) {
    if(nl<=l&&r<=nr) {
        ans[p]+=k;
        tag[p]+=k;
        return ;
    }
    push_down(p,l,r);
    ll mid=(l+r)>>1;
    if(nl<=mid)update(nl,nr,l,mid,ls(p),k);
    if(nr>mid) update(nl,nr,mid+1,r,rs(p),k);
    push_up(p);
}
ll query(ll q_x,ll q_y,ll l,ll r,ll p) {
    ll res=inf;
    if(q_x<=l&&r<=q_y)return ans[p];
    ll mid=(l+r)>>1;
    push_down(p,l,r);
    if(q_x<=mid)res=min(query(q_x,q_y,l,mid,ls(p)),res);
    if(q_y>mid) res=min(res,query(q_x,q_y,mid+1,r,rs(p)));
    return res;
}
void opc(ll cp,ll l,ll r,ll p,ll zhi) {
    if(l==r&&cp==l) {
        ans[p]=zhi;
        return;
    }
    ll res=0;
    ll mid=(l+r)>>1;
    push_down(p,l,r);
    if(cp<=mid) opc(cp,l,mid,ls(p),zhi);
    if(cp>mid) opc(cp,mid+1,r,rs(p),zhi);
    push_up(p);
    return;
}
int main() {
    ll a1,b,c,d,e,f;
    scan();
    build(1,1,n+1);
    opc(1,1,n+1,1,0);
    opc(a[1],1,n+1,1,0);
    update(1,a[1]-1,1,n+1,1,B);
    if(a[1]!=n+1)
        update(a[1]+1,n+1,1,n+1,1,A);
//  for(int j=1; j<=n+1; j++) {
//          cout<<query(j,j,1,n+1,1)<<" ";
//      }
//      cout<<endl;
    for(int i=2; i<=n; i++) {
        ll anss=query(1,a[i]-1,1,n+1,1);
        opc(a[i],1,n+1,1,anss);
        update(1,a[i]-1,1,n+1,1,B);
        if(a[i]!=n+1)
            update(a[i]+1,n+1,1,n+1,1,A);
//      for(int j=1; j<=n+1; j++) 
//          query(j,j,1,n+1,1);
    }
    cout<<query(1,n+1,1,n+1,1);
    return 0;
}

附:思考题 (我不会)

现在你有两个楼梯。有 n 个人排成一条队,每个人有一个通过楼梯的时间 $t_{i}$。然后你每次可以让一个人从其中一个楼梯上楼 (按排队的顺序)。因为楼梯过窄,后面的人不能超越前面的人,所以后面的人到达的时间一定大于等于前面的人的最慢到达时间 (前面所有的人到达之后他才能到达)。定义一个人上楼的不爽值是他最终上楼所花的实际时间-$t_i$。请你最小化所有人的不爽值之和。
n 1e5,t 1e9。

完结撒花!

分类: 文章

darken

华师一退役OIer,QQ:2578050796。 博客园:https://www.cnblogs.com/thedreammaker/

2 条评论

boshi · 2019年10月28日 2:58 下午

第二道题的链接貌似无效。
顺便推荐 CF809D

    darken · 2019年10月29日 5:57 下午

    谢谢提醒!
    不过大佬提供的这道题好像需要平衡树,而我不会…..

发表评论

电子邮件地址不会被公开。 必填项已用*标注