感觉好久没有写过这样单独一篇题目的博客了的说
昨天上大物课的时候ztc问了我这道题，然后我口胡了下感觉还挺有趣的
不过其它题目就没啥时间看了，正巧最近在练DP专题，就顺手记录一下吧
这题的数据范围和问题一眼区间DP的形式，直接设\(f_{l,r}\)表示区间\([l,r]\)的答案
刚开始naive地认为直接枚举一对相邻的满足要求的位置，但发现这样可能会分出长度为奇数的区间，而且对于操作的顺序也很难处理
因此后面转换了思路，考虑区间\([l,r]\)要全删完的话，\(a_l\)总会有一个与之对应的\(a_i\)，因此我们可以枚举和\(l\)匹配删除的位置\(i\)，则有转移：
\[f_{l,r}=\sum_{i=l+1}^r [a_l>a_k]\times f_{l+1,i-1}\times f_{i+1,r}\times coef(l,i,r) \]这个式子前面的部分都很好理解，但就是引入的\(coef(l,i,r)\)需要一些分析
考虑此时整个序列的删除操作被分为了三类，一类是\([l+1,i-1]\)这段区间的，记为\(A\)，另一类是\([i+1,r]\)这段区间的，记为\(B\)，剩下的就是这次枚举的操作\((a_l,a_i)\)，记为\(C\)
由于我们的DP中，\(A,B\)得到的结果已经包含了顺序，因此现在要做的就是在合法的前提下求出组合这三种删除操作的顺序
不难发现\(C\)操作必须放在所有的\(A\)操作最后，然后\(B\)操作要在保留它们之间原来的顺序的前提下，放入\(A,C\)操作序列的中间
（刚开始没想到\(B\)带序以为就是个\(a^b\)型的转移系数，后面发现不对劲）
考虑求出\(A,C\)操作序列中间（包括两端）可以插入的空隙数目，不难发现其实转移系数就是把\(B\)序列分成若干份，每一份可以为\(0\)的问题，直接上插板法就行
手玩一下转移系数就是：
\[coef(l,i,r)=C_{\frac{i-l+1}{2}+\frac{r-i}{2}}^{\frac{(r-l)}{2}} \]然后就做完了，总复杂度\(O(n^3)\)
#include<cstdio>
#include<iostream>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=505,mod=1e9+7;
int n,a[N],f[N][N],C[N][N];
inline int DP(CI l,CI r)
{
if (l>r) return 1; if (~f[l][r]) return f[l][r]; int ret=0;
for (RI i=l+1;i<=r;++i) if ((i-l+1)%2==0&&a[l]>a[i])
(ret+=1LL*DP(l+1,i-1)*DP(i+1,r)%mod*C[(i-l+1)/2+(r-i)/2][(r-i)/2]%mod)%=mod;
return f[l][r]=ret;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
for (C[0][0]=i=1;i<=n;++i) for (C[i][0]=j=1;j<=i;++j)
C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
return memset(f,-1,sizeof(f)),printf("%d",DP(1,n)),0;
}