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

· · 题解

模拟赛 T2。

1

考虑 DP，定义 dp_i 表示到达第 i 个导师家的最大体力值，则容易有

dp_i=B_i+\max_{j<i}\left\{dp_j-A\times \left\lceil\frac{T_i-T_j}{D}\right\rceil\right\}

把起点和终点都看成 B=0 的导师家，暴力转移即可。

时间复杂度 O(n^2)，期望得分 20pts。

2

考虑优化。

令 T_i=a_iD+b_i,T_j=a_jD+b_j，则有

\begin{aligned} \left\lceil\frac{T_i-T_j}{D}\right\rceil&=\left\lceil\frac{(a_i-a_j)D+(b_i-b_j)}{D}\right\rceil\\ &=a_i-a_j+[b_i>b_j] \end{aligned}

带回原式，有

\begin{aligned} dp_i&=B_i+\max_{j<i}\left\{dp_j-A\times \left(a_i-a_j+[b_i>b_j]\right)\right\}\\ &=B_i-A\times a_i+\max_{j<i}\{dp_j+A\times a_j-A[b_i>b_j]\} \end{aligned}

则

dp_i=B_i-A\times a_i+ \begin{cases} dp_j+A\times a_j-A &b_i>b_j\\ dp_j+A\times a_j &b_i\le b_j \end{cases}

注意到括号里的值与 i 无关，考虑以 b_i 为下标建权值线段树/树状数组，维护前后缀最大值即可。

动态开点的话时间复杂度为 O(n\log D)，离散化一下可以做到 O(n\log n)，期望得分 100pts。 :::success[Code]

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int maxn=1e5+10;
int K,M,D,A,N;
int T[maxn],B[maxn];
int a[maxn],b[maxn];
int dp[maxn];
struct Seg{
    int l,r;
    int max;
}tr[4*maxn];
void pushup(int id){
    tr[id].max=max(tr[id<<1].max,tr[id<<1|1].max);
}
void build(int id,int l,int r){
    tr[id].l=l; tr[id].r=r;
    if(l==r){
        tr[id].max=-1e18;
        return;
    }
    int mid=(l+r)>>1;
    build(id<<1,l,mid); build(id<<1|1,mid+1,r);
    pushup(id);
}
void update(int id,int x,int k){
    if(tr[id].l==tr[id].r){
        tr[id].max=max(tr[id].max,k);
        return;
    }
    int mid=(tr[id].l+tr[id].r)>>1;
    if(x<=mid) update(id<<1,x,k);
    else update(id<<1|1,x,k);
    pushup(id);
}
int query(int id,int l,int r){
    if(l<=tr[id].l&&tr[id].r<=r) return tr[id].max;
    int mid=(tr[id].l+tr[id].r)>>1,maxx=-1e18;
    if(l<=mid) maxx=max(maxx,query(id<<1,l,r));
    if(mid<r) maxx=max(maxx,query(id<<1|1,l,r));
    return maxx;
}
vector<int> vt;
int find(int x){
    return lower_bound(vt.begin(),vt.end(),x)-vt.begin()+1;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>K>>M>>D>>A>>N;
    for(int i=2;i<=N+1;i++) cin>>T[i]>>B[i];
    T[1]=K; B[1]=0; T[N+2]=M; B[N+2]=0;
    for(int i=1;i<=N+2;i++) a[i]=T[i]/D,b[i]=T[i]%D,vt.push_back(b[i]);
    sort(vt.begin(),vt.end());
    vt.erase(unique(vt.begin(),vt.end()),vt.end());
    build(1,1,vt.size());
    memset(dp,-0x3f,sizeof(dp));
    dp[1]=0;
    update(1,find(b[1]),A*a[1]);
    for(int i=2;i<=N+2;i++){
        int mx1=query(1,1,find(b[i])-1)-A;
        int mx2=query(1,find(b[i]),vt.size());
        dp[i]=B[i]-A*a[i]+max(mx1,mx2);
        update(1,find(b[i]),dp[i]+A*a[i]);
    }
    cout<<dp[N+2];
    return 0;
}

:::

3

赛时有人人类智慧过了，大致思路是按 \left\lfloor\frac{-T_i+D-1}{D}\right\rfloor 排序，然后取前 50 个点，然后就过了。

但是你谷数据很强啊，目前乱搞做法最高也就拿了 30pts。