[Codeforces]CF1077F2题解
本文最后更新于 104 天前,其中的信息可能已经有所发展或是发生改变。

一道简单的动态规划优化题。

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。
原文链接:https://www.codein.icu/cf1077f2/

题意

给你一个数列 $a$,你需要选择 $m$ 个元素,使得连续的 $k$ 个元素都至少有一个被选中。

需要你最大化选出来的所有数的和。

解法

容易想到动态规划,定义 $f(i,j)$ 为前 $i$ 个元素选了 $j$ 个,且最后一个为 $i$ 时的最大和。
连续 $k$ 个必须选一个,即限定转移范围为 $[i – k,i – 1]$,那么有转移方程:

$$f(i,j) = \max \limits _{i – k \le p \le i – 1}f(p,j – 1) + a_i$$
朴素转移是 $O(n^3)$ 的,但看到连续区间取最大值,可以想到用单调队列优化。
具体地,维护关于 $f(p,j – 1)$ 的 $[i – k,i – 1]$ 区间的最大值单调队列。最外层枚举选了的元素个数 $j$ 进行更新。
最终复杂度 $O(n^2)$.

空间上可以使用滚动数组稍微优化。
判断无解的话,最后选的一个元素一定在 $[n – k + 1,n]$ 的区间内,设置初值为负无穷大,而 $f(0,0) = 0$ 进行合法转移即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <ctype.h>
using namespace std;
const int bufSize = 1e6;
inline char nc() { static char buf[bufSize], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++; }
template<typename T> 
inline T read(T &r)
{
    static char c;
    r = 0;
    for (c = nc(); !isdigit(c); c = nc());
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r;
}
const int maxn = 5e3 + 100;
#define int long long
int n,k,x,a[maxn];
int cost[2][maxn],f[2][maxn],q[maxn],qt,qh;
signed main()
{
    read(n), read(k), read(x);
    for (int i = 1; i <= n; ++i) read(a[i]);
    int now = 0, last = 1;
    memset(f[last], ~0x3f, sizeof(f[last]));
    f[last][0] = 0;
    for (int j = 1; j <= x; ++j)  //choose j
    {
        qh = qt = 1, q[1] = 0;
        for (int i = 1; i <= n; ++i)
        {
            while (qt >= qh && i - q[qh] > k) ++qh;
            f[now][i] = f[last][q[qh]] + a[i];
            while (qt >= qh && f[last][q[qt]] <= f[last][i]) --qt;
            q[++qt] = i;
        }
        now ^= 1, last ^= 1;
    }
    int ans = -(1ll << 60);
    for (int i = n - k + 1; i <= n; ++i) ans = max(ans, f[last][i]);
    if (ans >= 0) printf("%lld\n", ans);
    else puts("-1");
    return 0;
}
本文标题:[Codeforces]CF1077F2题解
本文作者:Clouder
本文链接: https://www.codein.icu/cf1077f2/
转载请标明。
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇