odeforces Round 923 (Div. 3)

__vector__ · 2024-02-07 01:06:49 · 个人记录

倒开不幸被卡。

G 被 hack 了，请忽略以下。

一张图描述状态：

G

可以想到 dp 做法，并且看起来最重要的两个量是：

1. 当前的结尾位置 i
2. 前 i 个涂满，且延伸到 j \ge i 位置同样全部涂满。

设状态 dp_{i,j} 代表以 i 结尾，前 j 个涂满的最小代价。

以下对 dp 赋值默认是 chkmin

考虑转移：

• 第 i 个向左涂： dp_{i,max(y,i)} = min(dp_{k,y})$，注意 $k \lt i,y \ge i-a_i
• 第 i 个向右涂： dp_{i,max(y,min(n,i+a_i-1))} = min(dp_{k,y})$，注意 $k \lt i,y \ge i-1
• 第 i 个不涂： dp_{i,y} = min(dp_{k,y})$，注意 $k \lt i,y \ge i

还有一种特殊情况，在样例的 testcase11 中可以看见。
这种情况就是 a_i \ge i，此时可以这样转移：

做完了。

简单分析一下，本算法复杂度 O(n^3)，最多 10^4 组数据，n \le 100，n 总和最多 1000，为了使运算量最大，出题人应该设置 10 个 n=100 的数据，此时运算量 10^7，稳过。

A-F

A-E 没做，F 一直 WA。