Atcoder 贪心杂题

[AGC008B] Contiguous Repainting

有 N 个格子横向排列成一行。从左起第 i 个格子上写有整数 a_i。

一开始，所有格子都是白色的。你可以任意次数重复以下操作：

操作结束后，所有黑色格子上所写整数的总和即为得分。请你求出可能得到的最大得分。

考虑最后一次操作，一定会将一段长为 k 的区间变成白色或黑色。但是其余的操作，可以将其他的任何一个地方变成任意一种颜色。

枚举即可。

由 4 个正方形格子连接而成的形状称为“俄罗斯方块”（Tetromino）。我们将下图中的 7 种俄罗斯方块依次称为 I、O、T、J、L、S、Z 型。

すぬけ君分别拥有 a_I 个 I 型、a_O 个 O 型、a_T 个 T 型、a_J 个 J 型、a_L 个 L 型、a_S 个 S 型、a_Z 个 Z 型俄罗斯方块。他想从这些俄罗斯方块中选出 K 个，拼成一个高 2 行、宽 2K 列的矩形。拼放时需要遵守以下规则：

すぬけ君想要拼出尽可能大的矩形。请你求出 K 的最大值。

T、S、Z 三种形状不能选（拼不出来），单独的 O 肯定可行，每两个 I、J、L 也行，I+J+L 也行。

f(x) = 2 \left\lfloor \frac{x}{2} \right\rfloor,g(x) = 2 \left\lfloor \frac{x-1}{2} \right\rfloor

E_1 = \begin{cases} 3 + g(i) + g(j) + g(l), & \text{if } i \neq 0 \text{ and } j \neq 0 \text{ and } l \neq 0, \\ 0, & \text{otherwise}. \end{cases}

E_2 = f(i) + f(j) + f(l)

\text{ans} \leftarrow o + \max(E_1, E_2)

给定一个长度为 N 的数列 x。请判断是否存在一个数列 a 满足以下所有条件，如果存在，请构造出一个这样的 a。

对于每个 1 \leq i \leq N，在 a 中所有等于 i 的元素中，从左往右数第 i 个 i，它在整个 a 中的位置恰好是从左往右数的第 x_i 个位置。

注意到 x_i 越小的数显然就要先填。

能确定位置的先填，然后从前往后按照 x_i 从小到大的顺序填，再从后往前按照 x_i 从大往小的顺序填。

高桥君和青木君使用一个 H 行 W 列的格子进行游戏。在这个格子上有 N 个障碍物，第 i 个障碍物位于 (X_i, Y_i)。这里，将第 i 行第 j 列的格子表示为 (i, j)。此外，任意障碍物都不会在 (1,1)，并且 (1,1) 上放有一个棋子。

游戏由高桥君先手，二人轮流进行以下两种操作之一：

将棋子移动到相邻的格子。假设棋子当前在 (x, y)，高桥君只能将棋子移动到 (x+1, y)，青木君只能将棋子移动到 (x, y+1)。如果没有可以移动的格子，或者目标格子上有障碍物，则不能进行此操作。
不移动棋子，直接结束本回合，保持格子状态不变。

如果连续两回合都没有移动棋子，游戏立即结束。

高桥君希望让游戏持续尽可能多的回合（包括选择不移动棋子的回合），而青木君则希望让游戏尽快结束。请你求出在双方都采取最优策略的情况下，高桥君能够进行的回合数。

高桥君能动就动，青木君希望尽可能快的走到障碍物上方。不难发现，对于每一个 x，棋子能到的 y 是一个区间 [1,up_x]。统计出所有满足 y\leq up_x 的障碍物中 x 最小的点即可，答案为 x_{min}-1。