3 条题解
-
3
其实可以用优先队列,只是多带个 log 而已code:
#include<bits/stdc++.h> using namespace std; #define int long long const int N=1e6+5; int n,h[N],w[N],k,d; struct node{ int sum,h,id; }; bool operator < (node a,node b){ if(a.sum!=b.sum) return a.sum>b.sum; return a.h<b.h; } node makenode(int x,int y,int z){ node aa; aa.sum=x; aa.h=y; aa.id=z; return aa; } priority_queue<node> pq; signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>k>>d; for(int i=1;i<=n;i++) cin>>h[i]>>w[i]; pq.push(makenode(w[1],h[1],1)); for(int i=2;i<=n;i++){ node y=pq.top(); while(i-y.id>k){ pq.pop(); y=pq.top(); } if(h[i]>h[y.id]) pq.push(makenode(y.sum+w[i]+d,h[i],i)); else pq.push(makenode(y.sum+w[i],h[i],i)); } node y=pq.top(); while(y.id!=n){ pq.pop(); y=pq.top(); } cout<<y.sum; return 0; }
信息
- ID
- 929
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 52
- 已通过
- 18
- 上传者