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; }时间复杂度 ,但比线段树常数小,空间复杂度
信息
- ID
- 329
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- (无)
- 递交数
- 135
- 已通过
- 23
- 上传者