3 条题解

  • 3
    @ 2026-10-24 11:12:17

    三倍 经验

    其实可以用优先队列,只是多带个 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;
    }
    
    • @ 2026-10-24 11:48:39

      %%%

    • @ 2026-10-24 11:51:30

      pqpq 竟然能过?

      我赛时写了 pqpq 感觉不行,结果删掉重写 dddldddl,调代码花了 1h1h。

    • @ 2026-10-26 9:32:22

      %%%

  • 0
    @ 2026-10-26 9:57:56

    啧,我承认当我写了半小时快写完的题解结果不小心刷新掉的时候我是绝望的

    重写一遍吧

    正文: 60pts(理论上的但实际上因为数据水可以过): n^2^的20加上d=0单调队列板子的40 代码如下:

    #include<bits/stdc++.h>
    using namespace std;
    void lhhsyn(){
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);	
    } 
    int n,k,d;
    long long f[300005];
    struct node{
    	int h,w;
    }a[300005];
    int lhh(int x,int y){
    	if(a[x].h>=a[y].h)return d;
    	else return 0;
    }
    void syn(){//单调队列板子优化
    	deque<int> q;
    	q.push_back(1);
    	for(int i=2;i<=n;i++){
    		while(!q.empty()&&q.front()<i-k){
    			q.pop_front();
    		}
    		f[i]=min(f[i],f[q.front()]+a[i].w);
    		while(!q.empty()&&f[q.back()]>=f[i])q.pop_back();
    		q.push_back(i);
    	}
    	cout<<f[n];
    }
    int main(){
    	lhhsyn();
    	cin>>n>>k>>d;
    	for(int i=1;i<=n;i++){
    		cin>>a[i].h>>a[i].w;
    	}
    	for(int i=1;i<=n;i++){
    		f[i]=1e9;
    	}
    	f[1]=a[1].w;
    	if(d==0){
    		syn();
    		return 0;
    	}
    	for(int i=2;i<=n;i++){
    		for(int j=1;j<=min(k,i-1);j++){
    			f[i]=min(f[i],f[i-j]+a[i].w+lhh(i,i-j));
    		}
    	}
    	cout<<f[n];
    	return 0;
    }
    
    

    拿着这个代码的syn()可以去A掉这个和这个

    那接下来是100分解。 其实也很好理解,就是相较板子多考虑了个状态h,因为考虑到d=1,所以比一个值体力值大的一定不可能创造比他还大的价值(因为最多加一)所以可以不管。但如果相等就不太一样,留下(选择)高度更高的那个,因为他更不容易+1,然后就还是板子了

    代码如下:

    #include<bits/stdc++.h>
    using namespace std;
    void lhhsyn(){
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);	
    } 
    int n,k,d;
    long long f[300005];
    struct node{
    	int h,w;
    }a[300005];
    int lhh(int x,int y){
    	if(a[x].h>=a[y].h)return d;
    	else return 0;
    }
    void syn(){
    	deque<int> q;
    	q.push_back(1);
    	for(int i=2;i<=n;i++){
    		while(!q.empty()&&q.front()<i-k){
    			q.pop_front();
    		}
    		f[i]=min(f[i],f[q.front()]+a[i].w);
    		while(!q.empty()&&f[q.back()]>=f[i])q.pop_back();
    		q.push_back(i);
    	}
    	cout<<f[n];
    }
    deque<int> q1;
    int main(){
    	lhhsyn();
    	cin>>n>>k>>d;
    	for(int i=1;i<=n;i++){
    		cin>>a[i].h>>a[i].w;
    	}
    	for(int i=1;i<=n;i++){
    		f[i]=1e9;
    	}
    	f[1]=a[1].w;
    	if(d==0){
    		syn();//其实这个可以不要了但是对我的话选择不删 
    		return 0;
    	}
    	q1.push_back(1);
    	for(int i=2;i<=n;i++){
    		while(!q1.empty()&&q1.front()<i-k){
    			q1.pop_front();
    		}
    		f[i]=min(f[i],f[q1.front()]+a[i].w+((a[i].h>=a[q1.front()].h)?d:0));//一个小改动 
    		while(!q1.empty()&&f[q1.back()]>f[i])q1.pop_back();//还有这个地方要小于,小于等于的话下面那行没用了
    		while(!q1.empty()&&f[q1.back()]==f[i]&&a[q1.back()].h<=a[i].h)q1.pop_back();//唯一添加 
    		q1.push_back(i);
    	}
    	cout<<f[n];
    	return 0;
    }
    
    

    我觉得我无论是题解还是代码写的比lzm的要优质有没有懂的

    依旧你OJ模拟赛神秘数据,n^2^就能过了。话说我好歹还写了单调队列板子呢,lzm为什么对我意见那么大捏 最后观看这篇题解的您要是觉得对您有帮助请麻烦点个赞呗(´・ω・`)

    • 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我模拟赛的分数也比他高

    • 1

    信息

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