4 条题解
-
2
这里有一个无需单调队列 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; }时间复杂度 ,但比线段树常数小,空间复杂度
-
1
推销一下我写的线段树滚木,跑慢勿笑。
题意
给定 个整数,从中选出若干个数,但不能选择超过 个连续的数,最大化所选的数字的和。
数据规模
∈ , <= <= , ∈ 。
分析
看到题目就发现可以用单调队列做到 ,或像 那样用优先队列做到 ,但常数小于线段树(实测优先队列 ,线段树 )。
思路
设 表示前 个数中第 个数字不选和选的情况下,满足条件的最大总和。
显然的, = 设 表示第 到 个数的和。
然后考虑选择 。
当 ,有 = 。
当 时,,有 = 。
,有 = 。
我们观察到,转移方程中和 有关的项为 ,故可以直接使用线段树维护,实现 转移,每次算出 ,就执行一次 单点更新,复杂度同样是 。
数字比较大,记得开 。
代码
#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
先写一个暴力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
- 上传者