题解：P14439 [JOISC 2013] 考拉 / Koala

· · 题解

闲话

又被大手子拉过来做题了，他说做了三个小时，一定要让我尝尝。。。

正文

式子一

题意比较显然，所以我们可以很快地推出一个初始的转移方程，其中 dp_i 表示在位置 i 得到的最大体力值。

dp_i= \max (dp_i,dp_j+B_i-A),j\in[ \max (0,i-D),i-1]

这个转移方程很简单，但是美中不足的是，它与位置大小相关，这意味着使用单调队列优化上述式子，依旧是 \Theta(M) 的时间复杂度，这明显不行。

式子二

所以我们考虑换一种式子，其中 dp_i 表示在第 i 个关键点（起点为 0，终点为 n+1，导师家）时的最大体力值。

dp_i= \max (dp_j-A\times \left \lceil \frac{t_i-t_j}{D} \right \rceil )+B_i,j\in[0,i-1]

这个式子也比较好推，但是它的相关变量（t_i，t_j，dp_i，dp_j）都混在一起了，我们没办法快速维护只与 j 相关的变量。

难道我们只能每次遍历然后暴力转移吗？

式子三

显然不是。

考虑把向上取整的部分拆掉，把与 i 相关的部分拆出括号。

我们想到一种常见的定义：

\left \lceil \frac{a-b}{d} \right \rceil=(x-y)+[r_a>r_b],r_a\in[0,d-1],r_b\in[0,d-1]

其中 x=\left \lfloor \frac{a}{d} \right \rfloor，y=\left \lfloor \frac{b}{d} \right \rfloor，r_a\equiv x\bmod d，r_b\equiv y\bmod d，方括号为艾弗森括号。

这个式子我们带入回式子二中，就会得到：

dp_i= \max (dp_j+A\times q_j-A\times [r_i>r_j])+B_i-A\times q_i

其中 q_i 与上述 x 相同含义，q_j 与上述 y 相同含义。

式子四

这个艾弗森括号很恶心啊，它保留了最后一个与 i 相关的变量，我们考虑把它也拆掉。

惊奇地发现，这个括号只是一个幌子，我们只要分类讨论，分成余数的大小比较就可以了。

所以最后的式子就出来了：

dp_i= \max (dp_j+A\times q_j,dp_k+A\times q_k-A)+B_i-A\times q_i,q_j\in[r_i,D-1],q_k\in[0,r_i-1]

最终实现

我们费尽千辛万苦最终推出来的式子终于把所有的 i 从递推中摘了出来，但是看着上面的依托，我们到底要怎么优化呢？

我们发现每次都要在前面找两遍最大值，还要更新当前位置的最大值以便后续更新。

所以我们需要一种可以支持区间查询最大值，单点修改为最大值的数据结构，这明显就是线段树。

那么线段树是依据什么建立的？

我们发现，式子四的两个变量的取值只和它们的余数大小相关，所以我们把距离对 D 的余数作为下标建立线段树就可以成功转移了。

还有一点，D 和 t_i 的值域太大了，线段树存不下，这里可以采用动态开点或把余数离散化两种技巧，我选择了后者。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define V vector
#define FOR(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define pb push_back
const int INF=6e18+10,N=1e6+10;
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define mid ((a[x].l+a[x].r)>>1)
struct node{
    int l,r,maxn;
}a[N<<2];
void push_up(int x){
    a[x].maxn=max(a[ls(x)].maxn,a[rs(x)].maxn);
}
void build(int x,int l,int r){
    a[x].l=l;a[x].r=r;a[x].maxn=-INF;
    if(l==r) return;
    build(ls(x),l,mid);build(rs(x),mid+1,r);
}
void update(int x,int pos,int w){
    if(a[x].l==a[x].r){
        a[x].maxn=max(a[x].maxn,w);
        return;
    }
    if(pos<=mid) update(ls(x),pos,w);
    else update(rs(x),pos,w);
    push_up(x);
}
int query(int x,int L,int R){
    if(L>R) return -INF;
    if(a[x].l>=L&&a[x].r<=R) return a[x].maxn;
    if(R<=mid) return query(ls(x),L,R);
    else if(L>mid) return query(rs(x),L,R);
    return max(query(ls(x),L,R),query(rs(x),L,R));
}
#undef ls
#undef rs
#undef mid
int t[N],b[N],dp[N];
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int K,M,d,A,n;cin>>K>>M>>d>>A>>n;
    V<int>lsh;
    lsh.pb(K%d);
    FOR(i,1,n) cin>>t[i]>>b[i],lsh.pb(t[i]%d);
    lsh.pb(M%d);
    sort(lsh.begin(),lsh.end());
    lsh.erase(unique(lsh.begin(),lsh.end()),lsh.end());
    int siz=lsh.size();
    build(1,0,siz-1);
    int fir=lower_bound(lsh.begin(),lsh.end(),K%d)-lsh.begin();
    update(1,fir,A*(int)(K/d));
    dp[0]=0;
    t[n+1]=M,b[n+1]=0;
    FOR(i,1,n+1){
        int qi=t[i]/d,mod=lower_bound(lsh.begin(),lsh.end(),t[i]%d)-lsh.begin();
        int lef=query(1,0,mod-1);
        int rig=query(1,mod,siz-1);
        int lls=-INF;
        if(lef>-INF/2) lls=max(lls,lef-A);
        if(rig>-INF/2) lls=max(lls,rig);
        if(lls>-INF/2) dp[i]=lls-A*qi+b[i];
        else dp[i]=-INF;
        if(dp[i]>-INF/2) update(1,mod,dp[i]+qi*A);
    }
    cout<<dp[n+1];
    return 0;
}