专项训练dp总结

标签：总结 专项 若下 合法 deski 序列 一位 dp

作者在做题的时候深感自己dp水平的低下（几近为零），于是尝试逼迫自己搞懂每道题并写一点做题记录，本质上是为了避免自己成为只会抄题解的机器。。

1.[PA2021] Od deski do deski

首先，对于一个合法的序列f，若f+x为合法序列，那么f+x+x必然也为合法序列。

其次状态设计，设 \(f_{i,j,0/1}\) 表示序列的前 \(i\) 个，在后面放 \(j\) 种数可以变成合法的（注意这一位的设计会比较诡异，但是为了方便转移）,0/1表示当前这个序列是否合法。

考虑转移，对于第 \(i+1\) 位进行分讨，如果当前序列是合法的，则有

\[若下一位合法：f_{i+1,j,1}+=f_{i+1,j,1}+f_{i,j,1}*j \]

\[若下一位不合法：f_{i+1,j+1,0}+=f_{i,j,1}*(m-j) \]

标签：总结,专项,若下,合法,deski,序列,一位,dp
From： https://www.cnblogs.com/wann-042013/p/18470956