CF1982C Boring Day

Description

有大小为 $n$ 的数组 $a_i$ ，正整数 $l$ 、 $r$ 。数组中相邻的多个数可绑定为一组。一个数只能在一个组内。求最多能有多少组满足组内元素之和在 $[l,r]$ 内。

Solution

动态规划。

设 $f_i$ 表示数组只包含前 $i$ 个数时的答案。用总共为 $\Theta(n)$ 的双指针可求出最大的 $L$ ，满足 $[L,i]$ 中的元素之和在 $[l,r]$ 内。注意 $a_i$ 不一定要对答案产生贡献，此时直接取 $f_{i-1}$ 的值即可。可得转移方程

f_i=\max\{f_{i-1},f_{L-1}+1\}

答案即为 $f_n$ 。

双指针操作比较简单，可结合代码理解。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

int T, n, l, r, f[N], a[N], L, R, sum;

void WORK()
{
    memset(f, 0, sizeof(int) * (n + 5));
    scanf("%d%d%d", &n, &l, &r);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    L = R = 1; sum = a[1];
    for (int i = 1; i <= n; i++) {
        f[i] = max(f[i], f[i - 1]);
        while (R < i) sum += a[++R];
        while (sum - a[L] >= l && L < R) sum -= a[L++];
        if (l <= sum && sum <= r)
            f[i] = max(f[i], f[L - 1] + 1); 
    }
    printf("%d\n", f[n]);
} 

int main()
{
    scanf("%d", &T);
    while (T--) WORK();
    return 0;
}