【题解】P2467 [SDOI2010] 地精部落
hez_EX
·
·
题解
讨论板中提到了一种冷门 DP trick——连续段 DP，看了一下本题还没有相关的题解，写一篇权当补充。
感谢 @Richard_Whr 提到这种 DP。
感谢 @Charlie_ljk 提供的代码参考。
连续段 DP
这是一种 DP 思想，一般作用在有关排列的 DP 题上。常常会在考虑前 i 个元素的基础上记录现在存在 j 个合法的连续段，每次转移考虑合并连续段并使其保持合法状态，最终查询只有 1 个连续段时的 DP 值即答案。
本题
状态设计
-
- 第三维本身有四个取值，下文后缀
b 表示二进制数字。
-
- 取
00b，表示开头结尾的高度均未被钦定；
- 取
01b，表示开头的高度未被钦定，结尾的高度已被钦定。
- 取
10b，表示开头的高度已被钦定，结尾的高度未被钦定。
- 取
11b，表示开头结尾的高度均已被钦定；
状态转移方程
时刻记得：
- 目前插入的节点 i 是最高的。
- 每个连续段都以山谷开头结尾。
f[i][j][0] 的转移
如果我们不合并原有连续段，则上图红色标识的位置都可以加入一个新的连续段，即 j\leftarrow j-1 的过程。
如果我们趁着 i 的加入按照上面的红框选一段合并，则会减少一个连续段，即 j\leftarrow j+1 的过程。
所以简单转移方程为：
f[i][j][0]=f[i-1][j-1][0]\times j+f[i-1][j+1][0]\times j
f[i][j][1] 的转移
仍然先考虑不合并的情况，因为其尾部高度已经被钦定，所以将 i 作为一个独立段插入尾部是不行的，如上图尾部被钦定后是山峰或是山谷的状态是无关的，所以我们不必记录这个钦定的高度到底是多少。
对于利用 i 合并的情况也是一样的。
如果从一个没有钦定过尾部高度的地方转移过来，则也有两种情况，一种是 i 单独成段插入，一种是 i“黏附”在最后一段的尾端，后者也恰好能完美统计上以山峰结尾，这也能证明只要用类似的处理方法就能做到不遗漏。
于是：
f[i][j][1]=f[i-1][j-1][1]\times(j-1)+f[i-1][j+1][1]\times j+f[i-1][j-1][0]+f[i-1][j][0])
f[i][j][2] 的转移
同上 f[i][j][1]。
f[i][j][3] 的转移
想必有上述的分析，这个转移也差不多能解读了：
f[i][j][3]=f[i-1][j-1][3]\times(j-2)+f[i-1][j+1][3]\times j+f[i-1][j-1][2]+f[i-1][j][2]+f[i-1][j-1][1]+f[i-1][j][1]
初态
- 头尾不钦定，于是 f[1][1][0]=1；
- 尾钦定为 1，于是 f[1][1][1]=1；
- 头钦定为 1，于是 f[1][1][2]=1。
### 终态
当答案统计完毕时，头尾是多少肯定是一定的，~~不会处于钦定和未钦定的量子叠加态~~，故终态为考虑插入了前 $n$ 个数，只有 $1$ 个连续段且头尾都钦定的 $3$ 状态即 $f[n][1][3]$。
---
注意这种做法需要 $f$ 数组进行滚动优化空间。
注意取模。
## AC 代码
```cpp
#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;
inline void read(int &x)
{
char c=getchar();x=0;
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10-48+c,c=getchar();
}
int n,p,f[2][4205][4];
int main()
{
read(n);read(p);
f[1][1][0]=f[1][1][1]=f[1][1][2]=1;
for(int i=2;i<=n;i++)
for(int j=1;j<=i;j++)
{
f[i&1][j][0]=(1ll*f[(i-1)&1][j-1][0]*j%p+1ll*f[(i-1)&1][j+1][0]*j%p)%p;
f[i&1][j][1]=(1ll*f[(i-1)&1][j-1][1]*(j-1)%p+1ll*f[(i-1)&1][j+1][1]*j%p+f[(i-1)&1][j-1][0]+f[(i-1)&1][j][0])%p;
f[i&1][j][2]=(1ll*f[(i-1)&1][j-1][2]*(j-1)%p+1ll*f[(i-1)&1][j+1][2]*j%p+f[(i-1)&1][j-1][0]+f[(i-1)&1][j][0])%p;
f[i&1][j][3]=(1ll*f[(i-1)&1][j-1][3]*(j-2)%p+1ll*f[(i-1)&1][j+1][3]*j%p+f[(i-1)&1][j-1][2]+f[(i-1)&1][j][2]+f[(i-1)&1][j-1][1]+f[(i-1)&1][j][1])%p;
}
printf("%d",f[n&1][1][3]);
return 0;
}
```