CF1178F1 Short Colorful Strip

· · 题解

Short Colorful Strip

解题思路

由题目描述可知，n=m，所以每个颜色只能涂一次。又可知，颜色要从编号小的到编号大的涂，所以可以每次找出区间内颜色编号最小的位置作为基准点，记为 minid，将当前区间分 [l,minid] 和 [minid,r] 两个区间。

定义 dp_{i,j} 表示区间 [i,j] 的方案数。

对于区间 [l,minid]，方案数为：

\displaystyle\sum_{i=l}^{minid}\operatorname{dp}_{l,i-1}\times\operatorname{dp}_{i,minid-1}

对于区间 [minid,r]，方案数为：

\displaystyle\sum_{i=minid}^{r}\operatorname{dp}_{minid+1,i}\times\operatorname{dp}_{i+1,r}

最后，区间 [l,r] 的方案数可由由乘法原理求得，即：

\operatorname{dp}_{l,r}=\operatorname{dp}_{l,minid}\times\operatorname{dp}_{minid,r}

AC Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int Mod = 998244353;
const int Maxn = 500 + 5;
int n, m, a[Maxn];
int tmp[Maxn][Maxn];//区块l~r的方案数
inline int dp(int l, int r) {
    if (tmp[l][r]) {
        return tmp[l][r];
    } else if (l >= r) {
        tmp[l][r] = 1;
    } else {
        int minid = l, tmp1 = 0, tmp2 = 0;
        for (int i = l; i <= r; i++) {//求当前区块编号最小颜色
            if (a[i] < a[minid]) {
                minid = i;
            }
        }
        for (int i = l; i <= minid; i++) {
            tmp1 = (tmp1 + dp(l, i - 1) * dp(i, minid - 1) % Mod) % Mod;
        }
        for (int i = minid; i <= r; i++) {
            tmp2 = (tmp2 + dp(minid + 1, i) * dp(i + 1, r) % Mod) % Mod;
        }
        tmp[l][r] = tmp1 * tmp2 % Mod;
    }
    return tmp[l][r];
}
inline void work() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    dp(1, m);
    cout << tmp[1][m] % Mod << endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    work();
    return 0;
}