4 条题解

  • 2
    @ 2026-10-21 9:05:11

    这里有一个无需单调队列 DP 与线段树的做法,仅需优先队列。具体思路见注释

    
    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    const int N=1e6+5;
    int n,m,a[N],sum;
    struct node{
    	int sum;//当前的和 
    	int id;//上一个取的位置 
    };
    priority_queue<node> pq;//优先队列 
    node makenode(int x,int y){//数字转结构体 
    	node aa;
    	aa.sum=x; aa.id=y;
    	return aa;
    }
    bool operator < (node a,node b){//优先队列需要重载运算符 < 
    	return a.sum>b.sum;//先与总和小的尝试匹配 
    }
    signed main(){
    	ios::sync_with_stdio(0);
    	cin.tie(0); cout.tie(0);
    //	考虑转化,取若干个数,每隔最多 m 个数必须选一个数
    //	求其和的最小值,最后用总和减去它 
    	cin>>n>>m;
    	for(int i=1;i<=n;i++){
    		cin>>a[i];
    		sum+=a[i];//总和 
    	}
    	pq.push(makenode(0,0));//初始化 (选了总和为 0 的数,在位置 0)  
    	for(int i=1;i<=n;i++){
    		node x=pq.top();//由于可能重复匹配,因此先不弹出 
    		while(i-x.id>m+1){//优先队列的懒惰删除 
    		//由于第 i 位无法匹配的 i+? 也无法匹配,因此直接删除 
    			pq.pop();
    			x=pq.top();
    		}
    		pq.push(makenode(a[i]+x.sum,i));//将选 i 的情况加入队列 
    		//由于我们用最优情况去匹配,因此仅需将这种情况入队即可 
    	}
    	node x=pq.top();
    	while(n-x.id>m){//找到最优结果 
    		pq.pop();
    		x=pq.top();
    	}
    	cout<<sum-x.sum;//总和 - 最小的不选的和 = 答案 
    	return 0;
    }
    

    时间复杂度 O(Nlog⁡N)O(N\log N),但比线段树常数小,空间复杂度 O(N)O(N)

    AC记录

  • 1
    @ 2026-10-21 15:52:45

    【LOJ#10180】烽火传递

    • 1
      @ 2026-10-20 18:02:22

      推销一下我写的线段树滚木,跑慢勿笑。

      题意

      给定 NN 个整数,从中选出若干个数,但不能选择超过 MM 个连续的数,最大化所选的数字的和。

      数据规模

      NN ∈ [1,105][1,10^5],11 <= MM <= NN,AiAi ∈ [0,109][0,10^9]。

      分析

      看到题目就发现可以用单调队列做到 O(n)O(n),或像 wzcxwzcx 那样用优先队列做到 O(NlogN)O(NlogN),但常数小于线段树(实测优先队列 61ms61ms,线段树 141ms141ms)。

      思路

      设 fi,0/1f_{i,0/1} 表示前 ii 个数中第 ii 个数字不选和选的情况下,满足条件的最大总和。

      显然的,fi,0f_{i,0} = max(fi−1,0,fi−1,1)max(f_{i-1,0},f_{i-1,1}) 设 sumisum_i 表示第 11 到 ii 个数的和。

      然后考虑选择 AiA_i。

      当 i<=mi<=m,有fi,1f_{i,1} = sumisum_i。

      当 i>mi>m 时,? j∈[1,i−m]?~j∈[1,i-m],有 fi,1f_{i,1} = max(max(fi,1,fj,1+Ai),fj,0+Ai)max(max(f_{i,1},f_{j,1}+A_i),f_{j,0}+A_i)。

      ? j∈[i−m+1,i−1]?~j∈[i-m+1,i-1],有 fi,1f_{i,1} = max(fi,1,fj,0+sumi−sumj)max(f_{i,1},f_{j,0}+sum_i-sum_j)。

      我们观察到,转移方程中和 jj 有关的项为 fj,0−sumjf_{j,0}-sum_j,故可以直接使用线段树维护,实现 O(logN)O(logN) 转移,每次算出 fi,0f_{i,0},就执行一次 updateupdate 单点更新,复杂度同样是 O(logN)O(logN)。

      数字比较大,记得开 long longlong~long。

      代码

      #include <bits/stdc++.h>
      #define int long long 
      using namespace std;
      const int N = 1e5 + 5;
      int n, m, a[N], f[N][2];
      struct tree {
      	int l, r;
      	int maxx;
      }tr[N << 2];
      void pushup(int u) {
      	tr[u].maxx = max(tr[u << 1].maxx, tr[u << 1 | 1].maxx);
      }
      void build(int u, int l, int r) {
      	tr[u].l = l, tr[u].r = r;
      	if(l == r) {
      		tr[u].maxx = 0;
      		return ;
      	}
      	int mid = (l + r) >> 1;
      	build(u << 1, l, mid);
      	build(u << 1 | 1, mid + 1, r);
      	pushup(u);
      }
      void update(int u, int p, int x) {
      	if(tr[u].l == tr[u].r) {
      		tr[u].maxx = x;
      		return ;
      	}
      	int mid = (tr[u].l + tr[u].r) >> 1;
      	if(p <= mid) update(u << 1, p, x);
          else update(u << 1 | 1, p, x);
          pushup(u);
      }
      long long query(int u, int l, int r) {
      	if(tr[u].l >= l && tr[u].r <= r) {
      		return tr[u].maxx;
      	}
      	if(tr[u].l > r || tr[u].r < l || l > r) return 0;
      	int mid = (tr[u].l + tr[u].r) >> 1;
      	if(l > mid) return query(u << 1 | 1, l, r);
      	if(r <= mid) return query(u << 1, l, r);
      	return max(query(u << 1, l, r), query(u << 1 | 1, l, r));
      }
      long long sum[N];
      signed main() {
        ios :: sync_with_stdio(0);
        cin.tie(0), cout.tie(0);
      	cin >> n >> m;
      	for(int i=1; i<=n; ++i) {
      		cin >> a[i];
      		sum[i] = sum[i - 1] + a[i];
      	}
      	build(1, 1, n);
      	f[1][0] = 0, f[1][1] = a[1];
      	update(1, 1, 0 - a[1]);
      	for(int i=2; i<=m; ++i) f[i][1] = max(f[i - 1][1] + a[i], f[i - 1][0] + a[i]), f[i][0] = max(f[i - 1][1], f[i - 1][0]), update(1, i, f[i][0] - sum[i]);
      	for(int i=m+1; i<=n; ++i) {
      		f[i][1] = max(max(1LL * f[i][1], 1LL * f[i - 1][0] + a[i]), query(1, i - m, i - 1) + sum[i]);
      		f[i][0] = max(f[i - 1][1], f[i - 1][0]);
      		update(1, i, f[i][0] - sum[i]);
      	}
      	cout << max(f[n][0], f[n][1]);
      	return 0;
      } 
      
    • -1
      @ 2026-10-21 9:32:57

      先写一个暴力dp,写完就能发现可以单调队列优化(是个长度为m的滑动窗口)

      #include<bits/stdc++.h>
      #define int long long
      using namespace std;
      int n,m,a[100007],f[100007][2],l=1,r=1;
      pair<int,int> qu[100007];
      signed main(){
          ios::sync_with_stdio(0);
          cin.tie(0);
          cin>>n>>m;
          for(int i=1;i<=n;++i){
              cin>>a[i];
              a[i]+=a[i-1];
          }
          f[1][0]=a[1];
          qu[1]={1,a[1]};
          for(int i=2;i<=m;++i){
              f[i][1]=a[i];
              f[i][0]=a[i-1];
              while(l<=r&&qu[r].second>=a[i]-a[i-1]){
                  --r;
              }
              qu[++r]={i,a[i]-a[i-1]};
          }
          for(int i=m+1;i<=n;++i){
              f[i][0]=max(f[i-1][0],f[i-1][1]);
              f[i][1]=max(f[i][1],a[i]-qu[l].second);
              while(l<=r&&qu[l].first<=i-m){
                  ++l;
              }
              while(l<=r&&qu[r].second>=a[i]-f[i][0]){
                  --r;
              }
              qu[++r]={i,a[i]-f[i][0]};
          }
          cout<<max(f[n][0],f[n][1]);
          return 0;
      }
      
      • 1

      信息

      ID
      329
      时间
      1000ms
      内存
      256MiB
      难度
      8
      标签
      (无)
      递交数
      135
      已通过
      23
      上传者