[Luogu]P5858 Golden Sword
本文最后更新于 330 天前,其中的信息可能已经有所发展或是发生改变。

Before the Beginning

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

题意

题目传送门

有 $n$ 种原料,锅中可以同时存在 $w$ 种原料,每次放入前可以取出 $s$ 种原料。
放入第 $i$ 种原料,贡献为 $a_i \times 当前锅中原料种数$,且种数包括当前的一种。
求最大值。

解法

首先分析,如果 $a_i$ 恒为正数,那么肯定是保持最大容量时贡献值最大。
但有负数,就需要多加考虑了。
猜想进行动态规划,那么尝试定义状态。
首先,锅内种数肯定是状态中的一维,而最后放入了哪一种也一定是一维。
而这两维就足以准确地定义一个状态了。
那么定义:

$$ dp_{i,j} 代表放入第i种原料后,锅内有j种原料的最大贡献值。 $$

思考如何转移。每次放入,可以取出 $[0,s]$ 种原料,也就是可以从 $dp_{i-1,j-1}$ (取出 $0$ 种) 到 $dp_{i-1,j+s-1}$ (取出 $s$ 种) 间的状态转移得到 $dp_{i,j}$ 的状态。
不难列出方程:

$$ dp_{i,j} = \max(dp_{i-1,k},k \in [j-1,j+s-1])$$

那么如果朴素地进行枚举转移,复杂度为 $O(nws)$,显然是不可接受的。
但观察到连续区间最值这种结构,很显然可以用数据结构进行优化。
常用的是单调队列维护区间最值。
维护一个最大值单调队列,即可降去 $O(s)$ 的复杂度,达到 $O(nw)$ 的复杂度通过本题。

同时空间如果朴素地开 $O(nw)$ 也是不太能接受的,可以使用滚动数组优化。

代码

在敲单调队列的时候出了些神秘的锅,所以用了一种不容易出锅的写法。
需要注意的是初始化为负无穷大,避免在 $a_i$ 全为负数的情况输出 $0$。
另外,不开 long long 见祖宗……
总的来说,这题思路还是比较易得的,代码难度也一般。

#include <cstdio>
#include <cstring>
using namespace std;
template <typename T>
void read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = getchar(); c > '9' || c < '0'; c = getchar()) if (c == '-') flag = -1;
    for (; c >= '0' && c <= '9'; r = (r << 1) + (r << 3) + (c ^ 48), c = getchar());
    r *= flag;
}
const int maxn = 6000;
int n, w, s;
long long dp[2][maxn];
long long a[maxn];
int head, tail, q1, q2, q[maxn];
int main()
{
    read(n);
    read(w);
    read(s);
    for (int i = 1; i <= n; ++i)
        read(a[i]);
    int now = 0, last = 1;
    for (int i = 1; i <= n; ++i)
    {
        memset(dp[now], ~0x3f, sizeof(dp[now]));
        head = 1, tail = 0;
        q1 = q2 = 1;
        for (int j = 1; j <= i && j <= w; ++j)
        {
            while (q2 <= j + s - 1 && q2 <= w && q2 < i)
            {
                while (tail >= head && dp[last][q[tail]] <= dp[last][q2]) --tail;
                q[++tail] = q2;
                ++q2;
            }
            while (tail >= head && q[head] < j - 1) ++head;
            dp[now][j] = dp[last][q[head]] + a[i] * j;
        }
        now ^= 1;
        last ^= 1;
    }
    long long ans = -(1ll << 60);
    for (int i = 1; i <= w; ++i)
        ans = ans > dp[last][i] ? ans : dp[last][i];
    printf("%lld", ans);
    return 0;
}
本文标题:[Luogu]P5858 Golden Sword
本文作者:Clouder
本文链接: https://www.codein.icu/lp5858/
转载请标明。
暂无评论

发送评论 编辑评论

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