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

· · 题解

日本神题，真的牛逼，推出来的时候超级激动。

首先对于这个题，肯定是要用动态规划的，我们先设计出转移方程。

设 dp_i 表示到达第 i 个导师家里并休息后，体力的最大值，由于要走到前理事长的家，且走到那里不会回复体力，所以我们可以把前理事长的家视作第 n+1 个导师的家，然后回复的体力为 0；由于初始坐标也不一定在 0，所以我们还要把初始坐标也加进去，视作第 0 个导师的家，回复的体力也为 0。

那么对于这个暴力的转移方程，是很好想的。对于某个导师 i，它的位置可以从前面的导师的位置的最大体力值转移过来，然后我们取最大值，即：

\begin{aligned}dp_i=\max(dp_i,dp_j- \lceil \frac{t_i-t_j}{d} \rceil\times a +b_i ) \end{aligned}

上面的式子满足 0\le j<i，意思是，从前面那个导师走过来要消耗 dp_j- \lceil \frac{t_i-t_j}{d} \rceil\times a 的体力，因为你要刚好走到那个位置所以你要向上取整。

但是这样转移是 O(n^2) 的，考虑优化。

我们知道：

\begin{aligned}\lceil \frac{x-y}{d} \rceil=\lfloor \frac{x-y+d-1}{d} \rfloor \end{aligned}

并且：

\begin{aligned}\lfloor \frac{x-y+d-1}{d} \rfloor=\lfloor \frac{x}{d} \rfloor-\lfloor \frac{y}{d} \rfloor+(x \bmod d>y\bmod d) \end{aligned}

所以上面那个转移式子的第二项就可以写成：

\begin{aligned}dp_j- \lfloor \frac{t_i}{d} \rfloor\times a +\lfloor \frac{t_j}{d} \rfloor\times a-(t_i\bmod d>t_j\bmod d)\times a +b_i \end{aligned}

然后我们把跟 j 有关的项拿出来放到前面，变成：

\begin{aligned}dp_j +\lfloor \frac{t_j}{d} \rfloor\times a-(t_i\bmod d>t_j\bmod d)\times a- \lfloor \frac{t_i}{d} \rfloor\times a +b_i \end{aligned}

好的现在如果没有那个余数的限制，那么这个题就是一个非常基础的线段树优化的板子，只需要把前面的那一部分记下来然后放到线段树上后直接转移即可。

但是这个玩意有一个取模的限制，所以我们还得再讨论一下。

我们把那个余数的限制拆开，变成：

\begin{aligned}dp_j +\lfloor \frac{t_j}{d} \rfloor\times a-a- \lfloor \frac{t_i}{d} \rfloor\times a +b_i,(t_i\bmod d >t_j\bmod d) \end{aligned} \begin{aligned}dp_j +\lfloor \frac{t_j}{d} \rfloor\times a- \lfloor \frac{t_i}{d} \rfloor\times a +b_i,(t_i\bmod d \le t_j\bmod d) \end{aligned}

那么变成了这个形式后，我们发现转移跟余数有关，且每次转移要从前面余数比当前大的或比当前小的转移过来（当然也可能有从相等的情况转移过来）。

所以我们有了一个想法：按余数为下标来存。但是模数 d 太大了怎么办？离散化呗，我们先把所有的余数预处理出来，然后把余数离散化，存的时候按照余数离散化后的大小来存。

到了这里，这道题就差不多做完了，只需套上一个线段树板子，然后对于每个 i 去维护 dp_i +\lfloor \frac{t_i}{d} \rfloor\times a 的值即可，转移的时候从前面的最大值转移过来。

还要注意一些细节，比如前面提到的，边界的第 0 个导师家和第 n+1 个导师家别忘了也把余数给处理了。还有一点是初始化要赋一个极小值，这个答案好像最小能去到 -10^{18}。

::::success[AC code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10,inf=-8e18;
int k,m,d,a,n,stx,enx;
int dp[N],t[N],b[N];//dp[i]表示到第i个导师家里歇息的最大体力值
//(x-y+d-1)/d=x/d-y/d+(x%d>y%d) 
int f[N]; 
struct BIT{
    int t[N<<2];//存距离取模的余数为r的dp最大值 
    inline void push_up(int x){
        t[x]=max(t[x*2],t[x*2+1]);
        return;
    }
    inline void build(int l,int r,int x){
        t[x]=inf;
        if(l==r)return;
        int mid=l+r>>1;
        build(l,mid,x*2);
        build(mid+1,r,x*2+1);
        return;
    }
    void update(int pos,int l,int r,int x,int k){
        if(l==r){
            t[x]=max(t[x],k);
            //if(k==0)cout<<"pos="<<pos<<" l="<<l<<" r="<<r<<" t[x]="<<t[x]<<" x="<<x<<"\n";
            return;
        }
        int mid=l+r>>1;
        if(pos<=mid)update(pos,l,mid,x*2,k);
        else update(pos,mid+1,r,x*2+1,k);
        push_up(x);
    }
    inline int ask(int L,int R,int l,int r,int x){
        //if(L==R&&R==3)cout<<"x="<<x<<" l="<<l<<" r="<<r<<"\n";
        if(L<=l&&r<=R)return t[x];
        int mid=l+r>>1,res=inf;
        if(L<=mid)res=max(res,ask(L,R,l,mid,x*2));
        if(R>mid)res=max(res,ask(L,R,mid+1,r,x*2+1));
        return res; 
    }
}tree; 
vector<int> g;
int r[N],mp[N];//表示第i个坐标对d取模的余数（离散化后）,mp映射原来余数 
//dp[i]=dp[j]-(t[i]-t[j]+d-1)/d*a+b[i] = dp[j]+a* (t[j]/d) -a *(t[i]%d>t[j]%d) -a*(t[i]/d)+b[i] 
void lisanhua(){
    r[0]=stx%d,r[n]=enx%d;
    g.push_back(r[0]);g.push_back(r[n]);
    sort(g.begin(),g.end());
    g.erase(unique(g.begin(),g.end()),g.end());
    for(int i=0;i<=n;i++){
        int rr=r[i];
        r[i]=lower_bound(g.begin(),g.end(),r[i])-g.begin()+1;
        mp[r[i]]=rr;
    }
    return;
} 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>stx>>enx>>d>>a>>n;
    for(int i=1;i<=n;i++){
        cin>>t[i]>>b[i],dp[i]=inf;
        r[i]=t[i]%d;
        g.push_back(r[i]);
    }
    t[0]=stx;b[0]=0;
    n++;t[n]=enx;b[n]=0;
    lisanhua();dp[0]=0;
    int maxn=n+5;
    tree.build(1,maxn,1);
    //cout<<"maxn="<<maxn<<"\n";
    //cout<<"r[0]="<<r[0]<<"\n";
    tree.update(r[0],1,maxn,1,a*(t[0]/d));
    for(int i=1;i<=n;i++){
        int res1=tree.ask(1,r[i],1,maxn,1);//余数小于t[i]%d的部分 
        int res2=tree.ask(r[i],maxn,1,maxn,1);//余数大于等于它的部分 
        dp[i]=max(res1-a*(t[i]/d)-a+b[i],res2-a*(t[i]/d)+b[i]);
        tree.update(r[i],1,maxn,1,dp[i]+a*(t[i]/d));//修改 
    //  cout<<"res1="<<res1<<" res2="<<res2<<" dp["<<i<<"]="<<dp[i]<<" r["<<i<<"]="<<r[i]<<"\n";
    }
    cout<<dp[n]<<"\n";
    return 0;
}

::::