CF1178F1 Short Colorful Strip 题解
xuantianhao
2023-10-10 13:13:21
# [Short Colorful Strip](https://www.luogu.com.cn/problem/CF1178F1)
考虑设 $f[i,j]$ 表示：假设区间 $[i,j]$ 里面一开始所有格子的颜色都是相同的，那么，染成目标状态共有多少种染法。
我们找到 $[i,j]$ 中最小的那个颜色，设为 $mp$。则显然，我们下一步要染上 $mp$ 这种颜色。
设最终在位置 $p_{mp}$ 上染上了颜色 $mp$。则我们可以在所有这样的区间 $[k,l]$ 上染上 $mp(i \le k \le p_{mp} \le l \le j)$。
或许你会以为这意味着 $f[i,j]=\sum\limits_{k=i}^{p_{mp}}\sum\limits_{l=p_{mp}}^jf[i,k-1] \times f[k,l] \times f[l+1,j]$。
但是，这样是错误的，因为当 $[k,l]=[i,j]$ 时，$f[i,j]$ 便无法从子状态转移过来！
我们考虑拆开 $f[k,l]$。因为再往后的染色中，位置 $p_{mp}$ 一定没有再被染色过，因此有 $f[k,l]=f[k,p_{mp}-1] \times f[p_{mp}+1,l]$。
则
$$f[i,j]=\sum\limits_{k=i}^{p_{mp}} \sum\limits_{l=p_{mp}}^{j} f[i,k-1] \times f[k,p_{mp}-1] \times f[p_{mp}+1,l] \times f[l+1,j]$$
特殊定义一下，对于 $f[i,j]$，如果 $i>j$，则 $f[i,j]=1$。这也是为了转移的正确（在应用上述式子时可能会调用到这样的 $f[i,j]$。
上面的转移是 $O(n^4)$ 的；但当我们拆开两个 $\sum$，就可以把它化成 $O(n^3)$ 的。
$$f[i,j]=(\sum\limits_{k=i}^{p_{mp}}f[i,k-1] \times f[k,p_{mp}-1]) \times (\sum\limits_{l=p_{mp}}^jf[p_{mp}+1,l] \times f[l+1,j])$$
前后两个括号内的内容互不干涉，故可以分开计算。
复杂度 $O(n^3)$。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
const int N=510;
int n,m;
int num[N],f[N][N];
inline int read(){
char c=getchar();int f=1,x=0;
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int main(){
n=read();m=read();
for(int i=1;i<=n;i++) num[i]=read();
for(int i=1;i<=n+1;i++)for(int j=0;j<i;j++) f[i][j]=1;
for(int i=1;i<=n;i++) f[i][i]=1;
for(int l=2;l<=n;l++){
for(int i=1,j=i+l-1;j<=n;i++,j++){
int x=i,A=0,B=0;
for(int k=i;k<=j;k++) if(num[k]<=num[x]) x=k;
for(int k=x;k>=i;k--) (A+=(1LL*f[i][k-1]*f[k][x-1]%mod))%=mod;
for(int k=x;k<=j;k++) (B+=(1LL*f[x+1][k]*f[k+1][j]%mod))%=mod;
f[i][j]=1LL*A*B%mod;
}
}
printf("%d\n",f[1][n]);
return 0;
}
```