P9744

CSP前的晚自习本来想打板子的，但是没有做题的欲望，就来写题解了。 小清新 dp。 思路 先观察每一个操作，发现操作一最特殊，思考下它有什么性质。如果我们进行了一次以上的操作一，一定不是最优的。因为每次都会把前 \(i\) 个数都变成零，重复之后就会覆盖原来的操作，回到第一次操作的初始状态，这样前 ......

P9744 「KDOI-06-S」消除序列 我们可以很容易发现操作 1 只可能使用一次。 先考虑序列固定的情况下的做法。 我们设 \(f_i\) 表示 \(1\sim i\) 用操作 1，\(i+1\sim n\) 不用的最小值。（\(i\) 可以取 \(0\)，表示不用操作 1） 对于前半部分，先 ......

@目录DesciptionSolutionCode Desciption 给定一个长度为 \(i\) 的序列 \(v_1,v_2,\dots,v_n\)，初始时所有元素的值都为 \(1\)。 对于下标 \(i\) 有 \(3\) 种操作： 将 \(v_1,v_2,\dots,v_i\) 的值变为 \ ......

本题有多种解法，我这里先讲一个我的考场做法吧。 切入点 我们发现我们至多使用一次操作一，而剩下部分的 \(0\) 肯定是依靠操作二补全，操作三的作用只是用来填补操作一的空白的，所以我们发现我们对一个序列的操作一定是前一段用操作一和操作三，后一段用操作二。 思路1 一开始考虑暴力 \(O(n)\) 枚 ......

题目传送门 这道题在比赛时先花了一个小时理解好题意才打了一个 \(70\) 分的 \(O(n^2)\) 暴力。下午刚起床，有点困，还没进入状态，打得挺慢。 具体地，会发现操作实际上是在这个长度为 \(n\) 的序列找一个点 \(i\)，将 \([0,i]\) 通过操作 \(1\) 全变 \(0\)， ......