262144 Revisited

题目描述

Bessie 喜欢在手机上下载游戏来玩，尽管她觉得小小的触摸屏对她的大蹄子来说用起来相当笨拙。 她对自己正在玩的这款游戏尤其着迷。游戏从一个由 $N$ 个正整数组成的序列 $a_1,a_2,\ldots,a_N$ 开始（$2\le N\le 262,144$），每个数都在范围 $1\ldots 10^6$ 内。 在一步操作中，Bessie 可以取两个相邻的数字，并将它们替换为一个数字，该数字等于这两个数的最大值再加一（例如，她可以将相邻的一对 $(5,7)$ 替换为 $8$）。 游戏在进行 $N-1$ 次操作后结束，此时只剩下一个数字。目标是最小化这个最终数字。 Bessie 知道这个游戏对你来说太简单了。所以你的任务不仅是对 $a$ 进行最优操作，还要对 $a$ 的每一个连续子序列都进行最优操作。 请输出所有 $\frac{N(N+1)}{2}$ 个连续子序列的“最小可能最终数字”之和。

输入格式

第一行包含 $N$。 第二行包含 $N$ 个用空格分隔的整数，表示输入序列。

输出格式

输出一行，包含所求的总和。

6
1 3 1 2 1 10

115

提示

总共有 $\frac{6\cdot 7}{2}=21$ 个连续子序列。例如，对于连续子序列 $[1,3,1,2,1]$，最小可能的最终数字是 $5$，可以通过如下操作序列得到： original -> [1,3,1,2,1] combine 1&3 -> [4,1,2,1] combine 2&1 -> [4,1,3] combine 1&3 -> [4,4] combine 4&4 -> [5] 以下是每个连续子序列的最小可能最终数字： final(1:1) = 1 final(1:2) = 4 final(1:3) = 5 final(1:4) = 5 final(1:5) = 5 final(1:6) = 11 final(2:2) = 3 final(2:3) = 4 final(2:4) = 4 final(2:5) = 5 final(2:6) = 11 final(3:3) = 1 final(3:4) = 3 final(3:5) = 4 final(3:6) = 11 final(4:4) = 2 final(4:5) = 3 final(4:6) = 11 final(5:5) = 1 final(5:6) = 11 final(6:6) = 10 评分： 测试点 2-3 满足 $N\le 300$。 测试点 4-5 满足 $N\le 3000$。 在测试点 6-8 中，所有数值都不超过 $40$。 在测试点 9-11 中，输入序列是非递减的。 测试点 12-23 没有额外限制。 题目来源：Benjamin Qi

标签: USACO|2022|Platinum

来源

USACO|2022|Platinum