原题链接。
感觉吃了一坨大的。代码源编课程的时候是怎么想到把这么恶心的 DP 放进去的。我要拒绝完成代码源 Y4 课程了。
一开始想着定义一手 $dp_{i,j}$ 表示考虑第 $i$ 位为 $j$ 的情况数然后跑容斥，很明显的 $O(n^2)$（至少看起来是）。然后代码写一半突然发现这个转移有问题，如果中间夹了一段别的东西就直接升天了。心态 -5。
然后接下来我就在各种形如考虑第 $i$ 位及前面有 $k$ 个 $j$ 的情况数之类的状态，晕，心态 -999。
最终拉了一坨这样的东西：
设 $dp_{i,j}$ 表示考虑到第 $i$ 个数，第 $i$ 个数是 $j$ 的方案数。转移：
$$dp_{i,j} = \sum_{k=i-j \wedge [\forall p \in [k,i),p = j \vee p = -1]}^{i-1}\sum_{col \not = j} dp_{k,col}$$这是 $O(n^4)$ 的，不过比较好优化，预处理一个 $k$ 的起始位置，再来一发前缀和，这几步都是 $O(n^2)$，所以总体还是 $O(n^2)$。可以过。但是人类应该是想不出来吧。这是我的代码。
这题评蓝多少有点恶评了。应该评黑。