9744
P9744 「KDOI-06-S」消除序列
CSP前的晚自习本来想打板子的,但是没有做题的欲望,就来写题解了。 小清新 dp。 思路 先观察每一个操作,发现操作一最特殊,思考下它有什么性质。如果我们进行了一次以上的操作一,一定不是最优的。因为每次都会把前 \(i\) 个数都变成零,重复之后就会覆盖原来的操作,回到第一次操作的初始状态,这样前 ......
P9744 「KDOI-06-S」消除序列
P9744 「KDOI-06-S」消除序列 我们可以很容易发现操作 1 只可能使用一次。 先考虑序列固定的情况下的做法。 我们设 \(f_i\) 表示 \(1\sim i\) 用操作 1,\(i+1\sim n\) 不用的最小值。(\(i\) 可以取 \(0\),表示不用操作 1) 对于前半部分,先 ......
P9744 「KDOI-06-S」消除序列 题解
@目录DesciptionSolutionCode Desciption 给定一个长度为 \(i\) 的序列 \(v_1,v_2,\dots,v_n\),初始时所有元素的值都为 \(1\)。 对于下标 \(i\) 有 \(3\) 种操作: 将 \(v_1,v_2,\dots,v_i\) 的值变为 \ ......
P9744 消除序列 题解
本题有多种解法,我这里先讲一个我的考场做法吧。 切入点 我们发现我们至多使用一次操作一,而剩下部分的 \(0\) 肯定是依靠操作二补全,操作三的作用只是用来填补操作一的空白的,所以我们发现我们对一个序列的操作一定是前一段用操作一和操作三,后一段用操作二。 思路1 一开始考虑暴力 \(O(n)\) 枚 ......