4 条题解

  • 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;
    } 
    

信息

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