CF1178F1题解
根据题意，每次选择一个区间染色，我们可以发现这道题满足了区间 dp 的一些性质，即区间答案可以合并，大区间的答案可以由小区间的答案更新而来。那么我们就可以设 \(f_{i,j}\) 表示区间 \(i\) 到 \(j\) 的答案，那么接下来就考虑如何转移。然后考虑到题目要求从 \(1\) 到 \(n\) 进行染色，所以我们转移的时候先找到这段区间中颜色最小的一个地方，将其位置编号记为 \(pos\)，那么 \(f_{i,j}\) 的答案则从 \(\left[i,k-1\right]\),
\(\left[k,pos-1\right]\),\(\left[pos+1,l\right]\),
\(\left[l+1,j\right]\) 这四个区间更新而来，转移的时候枚举 \(k，l\)，时间复杂度 \(O(n^4)\)，还不足以通过本题。
考虑优化这个算法，注意到 \(pos\) 两边对答案的贡献是互不影响的，所以转移时可以分开计算 \(pos\) 左右的答案，将两边的答案相乘即可实现转移，时间复杂度 \(O(n^3)\)。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
const int inf=1e9;
const int N=510;
inline int read(){
int f=1,w=0;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
w=(w<<1)+(w<<3)+(c^48);
c=getchar();
}
return f*w;
}
int c[N];
int f[N][N];
int n,m;
signed main(){
n=read();m=read();
for(int i=1;i<=n;i++){
c[i]=read();
}
for(int i=1;i<=n+1;i++){
f[i][i]=1;
f[i][i-1]=1;//注意，在转移时可能出现第二维编号比第一维小1的情况
}
for(int len=1;len<n;len++){
for(int i=1;i+len<=n;i++){
int j=i+len;
int pos;
int minn=inf;
for(int k=i;k<=j;k++){
if(c[k]<minn){
minn=c[k];
pos=k;
}
}
int f1=0;
for(int k=i;k<=pos;k++){
f1=(f1+f[i][k-1]*f[k][pos-1])%mod;
}
int f2=0;
for(int k=pos;k<=j;k++){
f2=(f2+f[pos+1][k]*f[k+1][j])%mod;;
}
f[i][j]=f1*f2%mod;
}
}
cout<<f[1][n]<<endl;
return 0;
}