沉玉谷
每次可以删除颜色相同的连续段。
删除的次数、顺序不同，答案就不一样。
因此题目即为求合法的删除方案数。
看数据范围，\(N\) 才 \(50\)！因此我们需要 \(O(N^{4\sim 6})\) 时间复杂度的算法。
这么高时间复杂度，本蒟蒻只能想到 DP。
区间 DP。
设 \(dp_{len,l,k}\) 表示区间 \([l,l+len-1]\) 删除 \(k\) 次删完的方案数，考虑转移。
设 \(r=l+len-1\)。
转移得到 \(dp_{len,l,k}\) 可以这样想：
由区间 \([l,r-1]\) 后加一位 \(a_{r}\) 得到区间 \([l,r]\) 的答案。
- 分别删除区间 \([l,r-1]\) 和 \(a_r\)。
- 把 \(a_r\) 与 \(a_j(l\leq j\leq r-1,a_j=a_r)\) 一起合并。
第二种转移，我们需要 \(a_j,a_r\) 同一次删除，且区间 \([j+1,r-1]\) 必须在 \(a_j,a_r\) 被删掉之前先删掉，因此答案由区间 \([l,j]\) 和区间 \([j+1,r-1]\) 转移得到，因为我们只要 \(a_j\) 在第 \(k\) 次删除的方案，为了方便，我们将 DP 加一维 \(x\)，\(dp_{len,l,k,x}\) 表示区间 \([l,l+len-1]\) 删除 \(k\) 次删完且 \(a_r\) 刚好在第 \(x\) 次被删掉的方案数。
详细 DP 转移过程如下：
转移 \(dp_{len,l,k,x}\) 时，
-
初始化 \(dp_{len,l,k=1,x=1}\) 的值（为 \(0\) 或 \(1\)），判断区间 \([l,r]\) 是否能整块一次删掉。
-
如果区间 \([l,r-1]\ k-1\) 次删完是合法的，加上 \(dp_{len-1,l,k-1,1\leq x \leq k-1}\) 的答案。
-
对于第二种转移方式，若 \(j=r-1\)，\(a_r\) 在 \(a_j\) 被删除的那一次可以直接被一起删掉，加上 \(dp_{len-1,l,k,x}\) 的答案。
否则枚举区间 \(1\) 即 \([j+1,r-1]\) 或区间 \(2\) 即 \([l,j]\) 要删除几次删完。然后就可以算出 \(a_j\) 在删除区间 \([l,j]\) 的步骤中是在第几次被删除的（\(x_1\)），加上答案 \(dp_{len_1,l,k_1,x_1}\times dp_{len_2,l_2,k2}\times calc(x_1,k_2)\)。
其中 \(calc(x_1,k_2)=(x_1-1+k_2)!\div ((x_1-1)!\times k_2!)\)。计算区间 \(2\) 的 \(k_2\) 个删除步骤必须都在区间 \(1\) 的第 \(x_1\) 步骤前的方案数。想象为 \(k_2+(x_1-1)\) 个点排序，由于 \(k_2\) 个步骤和 \(x_1-1\) 个步骤的前后顺序分别是一定的，要除去 \(k_2\) 个点和 \(x_1-1\) 个点分别的排列数量。
最后答案为区间 \([1,n]\) 删除任意次删完且 \(a_n\) 在任意次被删掉的方案数。
时间复杂度 \(O(n^6)\)，（DP 状态 \(O(n^4)\)，转移 \(O(n^2)\)），由于常数很小，不会超时。
code
#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define il inline
using namespace std;
typedef long long ll;
const int N=51,mod=1e9+7;int n,a[N];
int dp[N][N][N][N];
int f[N][N][N];
int jc[N];
int ny[N];void add(int &a,int b){a=(1ll*a+1ll*b)%mod;
}
int ksm(int a,int b){int sum=1;while(b){if(b&1) sum=1ll*sum*a%mod;a=1ll*a*a%mod;b>>=1;}return sum;
}
int calc(int a,int b,int c){return 1ll*jc[a]*ny[b]%mod*ny[c]%mod;
}int main(){
// freopen("jade7.in","r",stdin);
// freopen("jade.out","w",stdout);sf("%d",&n);jc[0]=1;ny[0]=1;for(int i=1;i<=n;i++){jc[i]=1ll*jc[i-1]*i%mod;ny[i]=ksm(jc[i],mod-2);}for(int i=1;i<=n;i++){sf("%d",&a[i]);}for(int len=1;len<=n;len++){for(int l=1,r=l+len-1;r<=n;l++,r++){dp[len][l][1][1]=1;for(int i=l+1;i<=r;i++){if(a[i]!=a[i-1]) {dp[len][l][1][1]=0;break;}}f[len][l][1]=dp[len][l][1][1];for(int k=2;k<=len;k++){for(int x=1;x<=k;x++){if(dp[len-1][l][k-1][k-1]){add(dp[len][l][k][x],f[len-1][l][k-1]);}for(int i=l;i<=r-1;i++){if(a[i]!=a[r]) continue;if(i==r-1){add(dp[len][l][k][x],dp[len-1][l][k][x]);continue;}for(int k2=1;k2<k&&k2<x;k2++){int k1=k-k2,x1=x-k2;add(dp[len][l][k][x],1ll*dp[i-l+1][l][k1][x1]*f[r-1-(i+1)+1][i+1][k2]%mod*calc(x1-1+k2,x1-1,k2)%mod);}}add(f[len][l][k],dp[len][l][k][x]);}}}}int ans=0;for(int i=1;i<=n;i++){add(ans,f[n][1][i]);}pf("%d\n",ans);
}
