科技--连续段dp学习笔记
\(\color{lightgray}{oi 大家好，我是来介绍}\)\(\color{black}{黑}\)\(\color{lightgray}{科技的woiler}\)
科技--连续段dp
连续段dp是用来解决以下问题的：
定义一个序列 \(A\) 是合法的，当且仅当：
(设序列 \(A\) 的元素为 \(a_1,a_2,a_3...,a_n\)，s，t为制定的常量)
- \(a_1=s\)，\(a_n=t\)
- 若\(a_i>a_{i-1}\)则\(a_i>a_{i+1}\)
- 若\(a_i<a_{i-1}\)则\(a_i<a_{i+1}\)
定义 \(dp_{i,j}\) 表示当前确定了 \(i\) 个位置的数，这些数连成了 \(j\) 段。
我们从小向大加入数，那么每次加入新的数时就有几种方式：（加入的数不是 \(s\) 或 \(t\) 时）
- 合并两个段：
左右两边都小于他，一定合法。上一步有 \(j+1\) 段，这一步就有 \(j\) 个空可以插，贡献为：
\(dp_{i-1,j+1}*j\) - 放在一个段的左边/右边
这样就会有一边小于（之前的数），另一边大于（之后的数）这个数，一定不合法 - 新建一段：
由于后面的数一定比这个数大，所以一定合法，上一步有 \(j-1\) 段，就可以放在 \(j\) 个空里面，但是如果当前的数大于 \(s\) 的话，就不能放在最左边，同理如果当前的数大于 \(t\) 的话，就不能放在最右边了。贡献：
\((j-[i>s]-[i>t])*dp_{i-1,j-1}\)
模版代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[2020][2020],s,t,n,mod=1e9+7;
signed main(){
cin>>n>>s>>t;
dp[1][1]=1;
for(int i=2;i<=n;i++){
for(int j=1;j<=i;j++){
if(i!=s&&i!=t){
dp[i][j]=((j-(i>s)-(i>t))%mod*dp[i-1][j-1]%mod+j*dp[i-1][j+1]%mod+mod)%mod;
}
else{
dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%mod;
}
}
}
cout<<dp[n][1];
return 0;
}
然后回到这道题目。你会惊讶的发现：
不就是不给定 \(s\) 和 \(t\) 嘛
然后很容易想到再加一维用来表示 \(s\) 和 \(t\) 是否确定，然后每次转移都可以使当前转移的数成为 \(s\) 或 \(t\) 就可以咯
先思考 \(s\) 和 \(t\) 都没有放的情况：
和之前的式子类似，只不过现在 \(i\) 绝对比 \(s\) 和 \(t\) 小（因为 \(s\) 和 \(t\) 要之后才确认嘛）转移为：
\[dp[i][j][0][0]=j*dp[i-1][j-1][0][0]+j*dp[i-1][j+1][0][0]
\]
然后是 \(s\) 放了 \(t\) 没放的情况：
首先是正常的转移，此时 \(i\) 比 \(s\) 大，比 \(t\) 小，因此转移为
\[dp[i][j][1][0]=(j-1)*dp[i-1][j-1][1][0]+j*dp[i-1][j+1][1][0]
\]
然后可以是现在这一位放的是 \(s\) ，可以合并也可以新建一段，有：
\[dp[i][j][1][0]+=dp[i-1][j-1][0][0]+dp[i-1][j][0][0]
\]
综合一下就是：
\[dp[i][j][1][0]=dp[i-1][j-1][0][0]+dp[i-1][j][0][0]+(j-1)*dp[i-1][j-1][1][0]+j*dp[i-1][j+1][1][0]
\]
\(t\) 放了 \(s\) 没放的情况同理：
\[dp[i][j][0][1]=dp[i-1][j-1][0][0]+dp[i-1][j][0][0]+(j-1)*dp[i-1][j-1][0][1]+j*dp[i-1][j+1][0][1]
\]
然后是 \(s\) 和 \(t\) 都放了的情况：
首先是正常的转移，此时 \(i\) 比 \(s\) 和 \(t\) 都大，因此转移为
\[dp[i][j][1][1]=(j-2)*dp[i-1][j-1][1][1]+j*dp[i-1][j+1][1][1]
\]
然后现在也有可能是这一步放在头或尾：
\[dp[i][j][1][1]+=dp[i-1][j-1][1][0]+dp[i-1][j][1][0]+dp[i-1][j-1][0][1]+dp[i-1][j][0][1]
\]
最后整个式子：
\[dp[i][j][1][1]=(j-2)*dp[i-1][j-1][1][1]+j*dp[i-1][j+1][1][1]+dp[i-1][j-1][1][0]+dp[i-1][j][1][0]+dp[i-1][j-1][0][1]+dp[i-1][j][0][1]
\]
发现可以滚动。
ACcode
#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[2][5040][2][2],s,t,n,mod;
signed main(){
cin>>n>>mod;
dp[1&1][1][0][0]=1;
dp[1&1][1][1][0]=1;
dp[1&1][1][0][1]=1;
for(int i=2;i<=n;i++){
memset(dp[i&1],0,sizeof(dp[i&1]));
for(int j=1;j<=i;j++){
dp[i&1][j][0][0]=(j*dp[(i-1)&1][j-1][0][0]%mod+j*dp[(i-1)&1][j+1][0][0]%mod+mod)%mod;
dp[i&1][j][1][0]=(dp[(i-1)&1][j-1][0][0]+dp[(i-1)&1][j][0][0]+(j-1)*dp[(i-1)&1][j-1][1][0]%mod+j*dp[(i-1)&1][j+1][1][0]%mod)%mod;
dp[i&1][j][0][1]=(dp[(i-1)&1][j-1][0][0]+dp[(i-1)&1][j][0][0]+(j-1)*dp[(i-1)&1][j-1][0][1]%mod+j*dp[(i-1)&1][j+1][0][1]%mod)%mod;
dp[i&1][j][1][1]=((j-2)*dp[(i-1)&1][j-1][1][1]%mod+j*dp[(i-1)&1][j+1][1][1]%mod+dp[(i-1)&1][j-1][1][0]+dp[(i-1)&1][j][1][0]+dp[(i-1)&1][j-1][0][1]+dp[(i-1)&1][j][0][1]%mod+mod)%mod;
}
}
cout<<dp[n&1][1][1][1];
return 0;
}