题解：P11791 [JOI 2017 Final] 准高速电车 / Semiexpress

· · 题解

两个结论。

每个 B 车区间是独立的。即在两个 B 车之间放 C 车不会影响这段区间外的答案。

一个区间内到达不了的车站是一段后缀。

根据结论一，我们在算答案时需要枚举每个区间单独处理。根据结论二，在 C 车数量有限制的情况下，我们想要能到达的车站尽可能多，显然需要把 C 车尽量往后放，于是我们每次把区间内第一个坐 A 车到达不了的车站放 C 车，然后计算贡献。

我们需要找到贡献最大的前 k-m 个 C 车站，那么可以开一个优先队列，记录起始 B 车站，当前扩展到的 C 车站，贡献，边界，每次选取贡献最大的车站，将贡献加到答案里，扩展后再放回优先队列中。

#include<bits/stdc++.h>
#define pb push_back
#define ls x<<1
#define rs x<<1|1
#define vt vector<int>
#define ll long long
#define pp pair<ll,ll>
#define N 3010
#define ull unsigned long long
using namespace std;
const ll M=998244353;
const ll inf=1e18;
void add(ll &x,ll y) { if((x+=y)>=M) x-=M; }
void add(ll &x,ll y,ll z) { x=(x+y*z%M)%M; }
ll qm(ll x,ll y) {
    ll res=1;
    for(;y;x=x*x%M,y/=2) if(y&1) res=res*x%M;
    return res;
}
ll n,m,k,A,B,C,T,ans,a[N];
struct node{
    ll id,p,val,bj;//从第几个特快车站扩展 扩展到的点编号 贡献 当前段的边界
    bool operator<(const node& p) const{ return val<p.val; }
};
priority_queue<node> q;
void solve() {
    cin>>n>>m>>k>>A>>B>>C>>T; k-=m; 
    for(int i=1;i<=m;i++) cin>>a[i];
    for(int i=1;i<m;i++) {
        if(B*(a[i]-1)>T) break;  //到不了当前车站
        ans+=min((T-B*(a[i]-1))/A+1,a[i+1]-a[i]); //先加上坐A车的贡献
        int t=a[i]+(T-B*(a[i]-1))/A+1; //扩展到的新点
        if((t-a[i])*C+(a[i]-1)*B>T) continue;
        if(t>=a[i+1]) continue;  //到下一段了
        int p=(T-B*(a[i]-1)-C*(t-a[i]))/A+1;//坐A车的贡献
        if(t+p-1>=a[i+1]) p=(a[i+1]-t); //贡献到下一段了 多出来的贡献应该放到下一段考虑
        q.push({a[i],t,p,a[i+1]});
    } ans+=((a[m]-1)*B<=T); //特判最后一个车站能否到达
    while(q.size()&&k) {
        node s=q.top();q.pop();k--;
        int x=s.id,y=s.p;ans+=s.val;
        int t=y+(T-B*(x-1)-C*(y-x))/A+1; //新点
        if(T-B*(x-1)-C*(y-x+1)<0) continue; //超出T
        if(t>=s.bj) continue; //到下一段了
        int p=(T-B*(x-1)-C*(t-x))/A+1; //新点贡献
        if(t+p-1>=s.bj) p=(s.bj-t); //贡献到下一段了
        q.push({x,t,p,s.bj});
    } printf("%lld",ans-1); //车站1不算
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);int t=1;
    while(t--) { solve(); }
    return 0;
}