Luogu P2034(P2627) 选择数字

我做的第一道单调队列练习题,双倍经验:P2627修剪草坪

题目链接

  • 定义$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)}$

    1
    2
    3
    4
    5
    6
    //伪代码
    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$满足答案的单调性,可以用单调队列维护。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    //伪代码
    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;
    }

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#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;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×