Loading... 我做的第一道单调队列练习题,双倍经验:P2627修剪草坪 <!--more--> [题目链接](https://www.luogu.org/problem/P2034) - 定义$f(i)$表示前i个数进行选择,满足最长连续的数不超过k个的情况下,最大选数和是多少。 - 考虑转移,因为连续不能选择超过k个数,所以枚举不选择的那个点p,并且$i-k\leq p\leq i$,因为涉及求和,预处理$S_i$表示数列中前k项的和,所以推出状态转移方程: - $f(i)=max_{i-k\leq p\leq i}\{f(p-1)+(S_i-S_p)\}$ ```cpp //伪代码 for(int i = 1; i <= n; i++){ for(int p = i - k; p <= i; p++){ f[i] = max(f[i], f[p-1] + (s[i] - s[p])); } } ``` - 得到一个$O(nk)$的算法,但是$n\leq 100000,k\leq n$显然过不了,因此考虑单调队列优化。 - 先把方程当中与p无关的部分单独提出来,变成$f(i)=max_{i-k\leq p\leq i}\{f(p-1)-S_p\}+S_i$。 - 显然max里的$f(p-1)-S_p$满足答案的单调性,可以用单调队列维护。 ```cpp //伪代码 int q[N]; int l = 1, r = 0; for(int i = 1; i <= n; i++){ while(l <= r && q[l] < i - k) l++; //此时队列头就是最优情况 f[i] = f[q[l]-1] - sum[q[l]] + sum[i]; //插入当前元素,以便后面转移。 //插入之前要满足单调队列性质,如果一个元素比你靠前,还没你优,就可以踢他出去。 while(l <= r && f[q[r]-1]-sum[q[r]]<f[i-1]-sum[i]) r--; q[++r] = i; } ``` 代码: ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; int n, k; int a[100009]; ll f[100009], sum[100009], d[100009]; struct que{ int val, pos; }q[100009]; int head = 0, tail = 1; void push(int x){ d[x] = f[x - 1] - sum[x]; while(x >= k + 1 && d[x - k - 1] == q[tail].val) head++; while(q[tail - 1].val < d[x] && tail > head) tail--; q[tail].val = d[x]; q[tail++].pos = x; } int main(){ scanf("%d%d", &n, &k); for(int i = 1; i <= n; i++){ scanf("%d", &a[i]); sum[i] = sum[i - 1] + a[i]; } q[head].val = -0x3f3f3f3f; for(int i = 1; i <= n; i++){ push(i); f[i] = q[head].val + sum[i]; } printf("%lld\n", f[n]); return 0; } ``` Last modification:March 14, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用,请随意赞赏