deski

一道很抽象的 \(\text {dp}\)? 状态就比较抽象。注意到 \(m\) 有 \(10^9\)，肯定不能带到状态里。但是我们可以注意到：如果当前序列 \(S\) 已经合法，且有 \(S+x\) 合法，那么 \(S+x+x\) 也一定合法，因为我们可以把两个 \(x\) 消掉。因此，可以设计 ......

P8386 platelett 讲的题欸。 先考虑给定序列怎么做。 问题显然可以转化为能否将序列分成若干个子序列。令 \(f_i\) 表示前 \(i\) 个数是否能够删完。则有 \(f_i = f_j[a_i=a_j, f_j=1]\)。这样是 \(n^2\) 的，也无法扩展至所有数列的情况。 建立 ......

显然是一道计数 dp。 dp 状态应该是最难的一部分了，个人认为这种状态设计得比较巧妙。如果像我刚开始一样设 \(dp_{i,j}\) 表示序列中一共有 \(i\) 个数，序列最后一个数为 \(j\) 的合法方案数的话，那么方程就会变得很不好转移，因为我们不知道当前的 \(j\) 和之前的某些数能不 ......

[PA2021] Od deski do deski 看似简单，实则考察的是选手的 DP 基本功，如果像我一样只会观察性质就做不出来这题。 性质：合法的序列一定是由若干个子串按照顺序拼起来的，其中每个子串的开头和结尾是一样的。 然后的想法就是设 \(f_i\) 表示子串 \(i\) 能一次消掉的方案 ......

# P8386 [PA2021] Od deski do deski [洛谷：Od deski do deski](https://www.luogu.com.cn/problem/P8386) [LOJ3600 Od deski do deski](https://loj.ac/p/3600) # ......

计数数列个数，要满足能划分为若干个两端相等区间。 首先容易想到DP。 我想的是按段分阶段转移，显然不行，因为很容易算重，一个数列能有多种划分方案则会被算多次。 因此直接计数数列的每位，$g(i,j)$表示前$i$位有$j$种值存在位置的前一个数列满足条件的合法序列方案数，$f(i,j)$则为不合法序 ......