Description

给定序列 $a_1,a_2,\dots,a_n$。

每次操作可以从 $i$ 跳到 $j$，费用为 $\min\{a_i,a_{i+1},\dots,a_j\}\times (j-i)^2$。

对于每个 $k,1\le k\le n$，求出从 $1$ 到达 $k$ 的最小费用。

Read More

这一场题目难度应该还是挺高的，而且细节很多，一共交了五发 unsuccessful submission，尤其是在 C 上浪费了很多时间，感觉这场 C 应该放在 D 后面比较合理，当然 C 如果思路正确做起来也很快，思维难度很难衡量。

Read More

Merry Xmas.

Read More

Description

两个长度为 $n$ 的序列 $a_{1\dots n}$ 和 $b_{1\dots n}$，选择 $i_{1\dots k}$ 和 $j_{1\dots k}$，使得 $i_p\le j_p$，最小化 $\sum (a_{i_p}+b_{j_p})$。

Medium $1\le k\le n\le 2200$ 4s

Hard $1\le k\le n\le 500000$ 10s

Read More

C. Swap Game

为了让游戏过程更直观，我们将游戏过程修改一下：$a_{1\dots n}$ 中有且仅有一个数 $a_t$ 被锁定，初始为 $a_1$，两人轮流从未被锁定的数中选择一个 $a_i$，如果 $a_i=0$ 则获胜，否则 $a_t\leftarrow a_t-1$ 且被锁定的数改为 $a_i$。

Read More