题解 CF1766E 【Decomposition】

Leasier · 2022-12-19 08:14:57 · 题解

首先，0 肯定只能被分到一个单独的序列里，则接下来我们可以不讨论它，一个 a_i = 0 会产生 i(n - i + 1) 的总贡献。

现在，我们可以发现：扔掉 0 之后，至多只会有三个序列。

• 如果有 3，一定在第一个序列里。
• 可能存在暂时扔不进第一个序列的 1, 2，至多会再构成两个序列。

考虑 dp。设 dp_{i, j, k, l} 表示所有以 i 结尾的子段中，所得的第一个序列末项为 j，第二个为 k，第三个为 l 的方案数（若没有该序列则对应项为 0）。

每次遇到一个 a_i = 0 直接继承；a_i > 0 则枚举一个 j, k, l 作为加入 a_i 之前各个序列的结尾，讨论一下插入第几个序列即可。

答案：\displaystyle\sum_{i = 1}^n ([a_i = 0] i(n - i + 1) + \sum_{j = 0}^3 \sum_{k = 0}^3 \sum_{l = 0}^3 dp_{i, j, k, l}([j > 0] + [k > 0] + [l > 0]))

时间复杂度为 O(n)。

代码：

#include <stdio.h>

typedef long long ll;

int dp[7][7][7][7];

int main(){
    int n, cur = 0;
    ll ans = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        int a;
        scanf("%d", &a);
        dp[cur][0][0][0]++;
        if (a == 0){
            ans += (ll)i * (n - i + 1);
        } else {
            int nxt = cur ^ 1;
            for (int j = 0; j <= 3; j++){
                for (int k = 0; k <= 3; k++){
                    for (int l = 0; l <= 3; l++){
                        dp[nxt][j][k][l] = 0;
                    }
                }
            }
            for (int j = 0; j <= 3; j++){
                for (int k = 0; k <= 3; k++){
                    for (int l = 0; l <= 3; l++){
                        if (j == 0 || (j & a)){
                            dp[nxt][a][k][l] += dp[cur][j][k][l];
                        } else if (k == 0 || (k & a)){
                            dp[nxt][j][a][l] += dp[cur][j][k][l];
                        } else {
                            dp[nxt][j][k][a] += dp[cur][j][k][l];
                        }
                    }
                }
            }
            cur = nxt;
        }
        for (int j = 0; j <= 3; j++){
            for (int k = 0; k <= 3; k++){
                for (int l = 0; l <= 3; l++){
                    ans += dp[cur][j][k][l] * ((j > 0 ? 1 : 0) + (k > 0 ? 1 : 0) + (l > 0 ? 1 : 0));
                }
            }
        }
    }
    printf("%lld", ans);
    return 0;
}