P2467 地精部落 题解
比较恶心的一道线性dp。
要求1~N的排列，满足a[i-1]<a[i]>a[i+1]或a[i-1]>a[i]<a[i+1]，求这样的排列的个数。
既然是线性dp，那么状态一定和长度有关，一维的状态是否能解决呢？
思考后发现不行，由于很难直接从f[i-1]推出f[i]（实际上可以用组合数搞出来），考虑改用二维。定义\(f_{i,j}\)为1~i的排列，以j为开头且为山峰的方案数。
得到状态转移方程\(f_{i,j}=f_{i,j-1}+f_{i-1,i-j+1}\)这个转移方程应该如何理解呢？
首先\(f_{i,j}\)由两部分组成：第二位是j-1和第二位不是j-1的情况。
- 如果第二位不是j-1,可以直接把\(f_{i,j-1}\)里的j-1全部和j调换；
- 如果第二位是j-1，那么考虑第一位为山谷的j-1，长度为i-1的方案数。
- 第一位为山谷的数列的个数怎么求呢？我们发现\(f_{i-1,i-j+1}\)中的每一个序列都可以通过取每一位与i的差值得到那么考虑第一位为山谷的j-1，长度为i-1的方案，所以把它写进转移方程。
#include<bits/stdc++.h>
using namespace std;
int f[2][5005];
int n,q;
int main(){
cin>>n>>q;
f[0][2]=1;//边界条件
for(int i=3;i<=n;i++){
for(int j=2;j<=i;j++){
f[i&1][j]=(f[i&1][j-1]+f[(i-1)&1][i-j+1])%q;
}
}
int ans=0;
for(int j=2;j<=n;j++){
ans=(ans+f[n&1][j])%q;
}
cout<<ans*2%q<<endl;
}