P8810 [蓝桥杯 2022 国 C] 数组个数 题解

· · 题解

思路比较简单的一道题。

用的五维 dp，看到二维和三维的 dp 直接膜了 orz。

正文开始。

分析

不难看出 dp。

因为 b_i 的值只与 a_{i-1},a_i,a_{i+1} 有关，所以我们定义 b_i 被 a_{c_1},a_{c_2},...a_{c_p} 满足为在这些 a 中最大的一项恰好为 b_i。

用 dp_{i,j,0/1,0/1,z} 来表示此状态下的方案数。

其中：

显然，a_i 的最大值就是 \min(b_{i-1},b_i,b_{i+1})，又因为 b_i\le10，所以 a_i 的最大值也是 10。

状态转移方程比较复杂。

如果 i>1，那么我们需要枚举 a_i 和 a_{i-1}。

这时候存在两种情况：

注意：在选择 a_i 的时候，b_{i-1} 必须被 a_{i-2},a_{i-1},a_i 满足，原因显然。

但当 i=1 时，应该单独讨论，因为 a_1 的选择会影响到 dp 数组的第 4 项，而 i\ge2 则不会。思路跟 i\ge2 的情况类似，不再赘述。

最后统计答案时，我们有几种情况：

最后，记得取模。

AC Code

臭长臭长的代码 qwq。

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
const int MOD = 1e9 + 7;

int n;
int dp[N][11][2][2][11], b[N], am[N];
int st;

inline int nxt (int idx) {
    return ((idx + 1) % n);
}

inline int pre (int idx) {
    return ((idx - 1 + n) % n);
}

int m (int x) {
    if (x < MOD) return x;
    return x - MOD;
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for (int i = 0;i < n;i++) cin >> b[i];
    for (int i = 0;i < n;i++) am[i] = min(b[pre(i)], min(b[i], b[nxt(i)]));
    for (int i = 0;i <= am[0];i++) if (i < b[0]) dp[0][i][0][0][i] = 1; else dp[0][i][1][1][i] = 1;
    for (int x = 0;x <= am[0];x++) for (int st = 0;st <= 1;st++) for (int j = 0;j <= am[1];j++) {
        if (j < b[1] && x < b[1]) {
            if (j < b[0]) dp[1][j][0][st][x] += m(dp[0][x][0][st][x] + dp[0][x][1][st][x]), dp[1][j][0][st][x] = m(dp[1][j][0][st][x]);
            else dp[1][j][0][1][x] += m(dp[0][x][0][st][x] + dp[0][x][1][st][x]), dp[1][j][0][1][x] = m(dp[1][j][0][1][x]);
        }
        else {
            if (j < b[0]) dp[1][j][1][st][x] += m(dp[0][x][0][st][x] + dp[0][x][1][st][x]), dp[1][j][1][st][x] = m(dp[1][j][1][st][x]);
            else dp[1][j][1][1][x] += m(dp[0][x][0][st][x] + dp[0][x][1][st][x]), dp[1][j][1][1][x] = m(dp[1][j][1][1][x]);
        }
    }
    for (int i = 2;i < n;i++) {
        int p = i - 1;
        for (int x = 0;x <= am[0];x++) for (int st = 0;st <= 1;st++) {
            for (int j = 0;j <= am[i];j++) {
                for (int z = 0;z <= am[p];z++) {
                    if (j < b[i] && z < b[i]) {
                        if (j < b[p]) dp[i][j][0][st][x] += dp[p][z][1][st][x];else dp[i][j][0][st][x] += m(dp[p][z][0][st][x] + dp[p][z][1][st][x]);
                        dp[i][j][0][st][x] = m(dp[i][j][0][st][x]);
                    }
                    else {
                        if (j < b[p]) dp[i][j][1][st][x] += dp[p][z][1][st][x];
                        else dp[i][j][1][st][x] += m(dp[p][z][0][st][x] + dp[p][z][1][st][x]);
                        dp[i][j][1][st][x] = m(dp[i][j][1][st][x]);
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int x = 0;x <= am[0];x++) for (int i = 0;i <= am[n - 1];i++) {
        ans += dp[n - 1][i][1][1][x]; ans = m(ans);
        if (i >= b[0]) ans += dp[n - 1][i][1][0][x];
        if (x >= b[n - 1]) ans += dp[n - 1][i][0][1][x];
        ans = m(ans);
    }
    cout << ans << endl;
    return 0;
}