摘要：
CodeForces-1178F1 Short Colorful Strip 区间DP 结合数据范围，我们可以认为染色方案的数量表示为具有间隔DP的相同颜色。限制：当给定的最终颜色被染色时，确定该间隔中的下一个颜色，即该间隔中最小值。你可以记住位置。此时，我们知道在枚举的染色间隔中只有一个点，因此和将被染色为其他颜色，因此整个间隔被分成四个部分，成为一个独立的子问题，所以我们可以使用namespacestd来DP[DP[l][r]=sum_{lleqileqp}sum_[pleqjleqr}DP[l][i-1]imesdp[i][p-1]imersdp[p+1][j]imestp[j+1][r]=]注意边界设置#includec；forc[i]=rd（）；fordp[i][i]=1；对于｛for｛intpos=l，l=0，R=0；forifpos=i；forL+=dp[l][i-1]*dp[i][pos-1]%MOD，l%=MOD；对于R+=dp[pos+1][i]*dp[i+1][l+len]%MOD；dp[l][l+len]=l*R%MOD；}}cout
题意
给定(0-n) 一共 (n+1)种颜色，现有(m)段初始时刻颜色都是0的纸，对这张纸的段进行操作，第(i)次操作会选择第(l)段到第(r)段纸进行区间染色，条件是这段此时必须为同种颜色，染为(i)。给出最终的每一段的颜色，问共有多少种染色方案，注意本题中(n = m)且每种颜色都会在最终的段中出现
[1 leq nleq500,n = m\ 1 leq c_i leq n ]
分析
做(CF)题自然要先挖掘性质，注意到此题的性质在于(n = m) ，染色时必须选择相同的颜色染色，这说明我们不能跨区间染色，且填某个颜色时的区间一定包含最终的那个位置。
再结合数据范围 想到用区间DP来做
令(dp[l][r])表示([l,r])为同一种颜色时的染色方案数，限制：题给的最终颜色
因此染色时，对这个区间的下一个颜色是确定的，也就是这段中最小值，不妨记位置作(p)，此时枚举(p)的染色区间([i,j])，我们知道最终只有(p)一个点，因此([i,p - 1])和([p+1,j])都会被染成其他颜色，于是整个区间([l,r])就被分为四个部分，成为了独立的子问题，于是可以DP了
[dp[l][r] = sum_{l leq i leq p}sum_{pleq j leq r} dp[l][i - 1] imes dp[i][p - 1] imes dp[p + 1][j] imes dp[j + 1][r] \ = (sum_{l leq i leq p} dp[l][i - 1] imes dp[i][p - 1] )(sum_{p leq j leq r}dp[p+1][j] imes dp[j + 1][r]) ]
代码
注意边界的设置
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll rd(){
ll x = 0;
char ch = getchar();
while(ch < '0' || ch > '9') {
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = x * 10 + ch - '0';
ch = getchar();
}
return x;
}
const ll MOD = 998244353;
int dp[505][505];
int main(){
int n = rd();
int m = rd();
vector<int> c(n + 1,0);
for(int i = 1;i <= n;i++)
c[i] = rd();
for(int i = 1;i <= n + 1;i++)
dp[i][i - 1] = dp[i][i] = 1;
for(int len = 1;len < n;len++){
for(int l = 1;l + len <= n;l++){
int pos = l,L = 0,R = 0;
for(int i = l;i <= l + len;i++)
if(c[i] < c[pos]) pos = i;
for(int i = l;i <= pos;i++)
L += (ll)dp[l][i - 1] * dp[i][pos - 1] % MOD,L %= MOD;
for(int i = pos;i <= l + len;i++)
R += (ll)dp[pos + 1][i] * dp[i + 1][l + len] % MOD,R %= MOD;
dp[l][l + len] = (ll) L * R % MOD;
}
}
cout << dp[1][n];
}