3 条题解

  • 0
    @ 2026-10-24 11:42:14

    三倍 经验

    O(n)O(n) 单调队列 DPDP 板子,无需多言。

    不过不要忘记 ∗d*d,否则 100100→6060。

    另外,建议加强数据,使 lhhlhh 等人的 O(n2)O(n^2) 做法仅获得 1010 分。(不然这题不就成了下位橙了)

    (最好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;
    }
    
    • @ 2026-10-26 8:30:20

      题目里说了60部分分你这个乐子

    • @ 2026-10-26 8:32:50

      不过N方拿全分确实比较神秘,建议改成题目描述中说的那样N方20,d=0 40

    • @ 2026-10-26 8:35:32

      lzm真招啊,自己比赛连T1唐题都没过还在这说T2数据怎么怎么样自己连题目描述都不看就说十分也别给,看似很大公无私实则就是觉得他没考过我急了,实则不说60就算给我算20我模拟赛的分数也比他高

信息

ID
929
时间
1000ms
内存
256MiB
难度
6
标签
(无)
递交数
52
已通过
18
上传者