P3648 [APIO2014]序列分割

    • 1.1K通过
    • 4.7K提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 前缀和 斜率优化 枚举,暴力 APIO 2014 Special Judge
  • 难度 省选/NOI-
  • 时空限制 2000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    你正在玩一个关于长度为 $n$ 的非负整数序列的游戏。这个游戏中你需要把序列分成 $k + 1$ 个非空的块。为了得到 $k + 1$ 块,你需要重复下面的操作 $k$ 次:

    选择一个有超过一个元素的块(初始时你只有一块,即整个序列)

    选择两个相邻元素把这个块从中间分开,得到两个非空的块。

    每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。

    输入输出格式

    输入格式:

    第一行包含两个整数 $n$ 和 $k$。保证 $k + 1 \leq n$。

    第二行包含 $n$ 个非负整数 $a_1, a_2, \cdots, a_n$ $(0 \leq a_i \leq 10^4)$,表示前文所述的序列。

    输出格式:

    第一行输出你能获得的最大总得分。

    第二行输出 $k$ 个介于 $1$ 到 $n - 1$ 之间的整数,表示为了使得总得分最大,你每次操作中分开两个块的位置。第 $i$ 个整数 $s_i$ 表示第 $i$ 次操作将在 $s_i$ 和 $s_{i + 1}$ 之间把块分开。

    如果有多种方案使得总得分最大,输出任意一种方案即可。

    输入输出样例

    输入样例#1: 复制
    7 3
    4 1 3 4 0 2 3
    输出样例#1: 复制
    108
    1 3 5

    说明

    你可以通过下面这些操作获得 $108$ 分:

    初始时你有一块 $(4, 1, 3, 4, 0, 2, 3)$。在第 $1$ 个元素后面分开,获得 $4 \times (1 + 3 + 4 + 0 + 2 + 3) = 52$ 分。

    你现在有两块 $(4), (1, 3, 4, 0, 2, 3)$。在第 $3$ 个元素后面分开,获得 $(1 + 3) \times (4 + 0 + 2 + 3) = 36$ 分。

    你现在有三块 $(4), (1, 3), (4, 0, 2, 3)$。在第 $5$ 个元素后面分开,获得 $(4 + 0) \times (2 + 3) = 20$ 分。

    所以,经过这些操作后你可以获得四块 $(4), (1, 3), (4, 0), (2, 3)$ 并获得 $52 + 36 + 20 = 108$ 分。

    限制与约定

    第一个子任务共 11 分,满足 $1 \leq k < n \leq 10$。

    第二个子任务共 11 分,满足 $1 \leq k < n \leq 50$。

    第三个子任务共 11 分,满足 $1 \leq k < n \leq 200$。

    第四个子任务共 17 分,满足 $2 \leq n \leq 1000, 1 \leq k \leq \min\{n - 1, 200\}$。

    第五个子任务共 21 分,满足 $2 \leq n \leq 10000, 1 \leq k \leq \min\{n - 1, 200\}$。

    第六个子任务共 29 分,满足 $2 \leq n \leq 100000, 1 \leq k \leq \min\{n - 1, 200\}$。

    感谢@larryzhong 提供的加强数据

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。