1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
#include<bits/stdc++.h>
using namespace std;
constexpr int maxn=3005;
int n,m,k,a,b,c,t;
long long ans,totc;
long long s[maxn];
priority_queue<int>q;
signed main(){
scanf("%d%d%d%d%d%d%d",&n,&m,&k,&a,&b,&c,&t);
k-=m;
for(int i=1;i<=m;i++)scanf("%lld",&s[i]);
for(int i=1;i<m;i++){
for(int ind=s[i],totc=0;ind<s[i+1];){//考虑每一块
totc++;
if(t-(s[i]-1)*b<(ind-s[i])*c)break;//如果再坐快速列车也到不了
int nxt=(t-(s[i]-1)*b-(ind-s[i])*c)/a+1;//否则计算还能做几站
if(ind+nxt>=s[i+1]){//如果到下一块去了
nxt=s[i+1]-ind;//那就到下一块开始之前
ind=s[i+1];
}
ind+=nxt;
if(totc==1)ans+=nxt;
else q.push(nxt);
if(totc>=k)break;//超过k站了，考虑下一个
}
}
if(t>=(n-1)*b)ans++;//能达到最后一个特急就加一
while(!q.empty()){
if(k==0)break;
k--;//一个个安排
ans+=q.top();
q.pop();
}
printf("%lld",ans-1);
}
|
然后用一个优先队列去维护到哪里能赚到的贡献最多，这里只取前 $k$ 个。做完了。