3 条题解
-
0
单调队列 板子,无需多言。
不过不要忘记 ,否则 →。
另外,建议加强数据,使 等人的 做法仅获得 分。(不然这题不就成了下位橙了)
(
最好10分也别给。)#include <bits/stdc++.h> using namespace std; const int N = 3e5 + 5; int n, k, d, h[N], w[N], f[N]; struct node { int hh, fv, id; }; deque<node> q; int solve() { f[1] = w[1], q.push_back({h[1], f[1], 1}); for(int i=2; i<=k; ++i) { node np = q.front(); f[i] = np.fv + w[i] + (np.hh <= h[i]) * d; while(q.back().fv > f[i] && q.size()) q.pop_back(); while(q.back().fv == f[i] && q.back().hh < h[i] && q.size()) q.pop_back(); q.push_back({h[i], f[i], i}); } for(int i=k+1; i<=n; ++i) { while(q.front().id < i - k && q.size()) q.pop_front(); node np = q.front(); f[i] = np.fv + w[i] + (np.hh <= h[i]) * d; while(q.back().fv > f[i] && q.size()) q.pop_back(); while(q.back().fv == f[i] && q.back().hh < h[i] && q.size()) q.pop_back(); q.push_back({h[i], f[i], i}); } while(!q.empty()) q.pop_front(); return f[n]; } int main() { scanf("%d%d%d", &n, &k, &d); for(int i=1; i<=n; ++i) { scanf("%d%d", &h[i], &w[i]); } printf("%d\n", solve()); return 0; }
信息
- ID
- 929
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 52
- 已通过
- 18
- 上传者