题解：P13890 [蓝桥杯 2023 省 Python A] 奇怪的数

· · 题解

P13890 [蓝桥杯 2023 省 Python A] 奇怪的数 【题解】

一道不错的练手动规

题目简述

要求输出满足以下条件的长度为 n 的数的个数：

思路

核心观察要点

  1. 每个数位的取值范围固定：奇数位有 5 种选择，偶数位有 5 种选择

  2. 约束条件只涉及连续 5 个数位，因此可以用最近 4 个数位的状态来推导新的状态

动规部分

代码实现很简单；

首先定义一个四维 dp 表示最后四个数位的索引为 a,b,c,d 时的合法数的数量。这里的索引对应预设的取值数组：

// v[0]存奇数位，v[1]存偶数位
int v[2][5]={{1,3,5,7,9},{0,2,4,6,8}};

其次，列状态转移方程：当新增第 5 个数位 e 时，需要检查这 5 个数位的和是否 \le m。若合法，则状态从 (a,b,c,d) 转移到 (b,c,d,e),具体的：

// 计算5个连续数位的和
int sum=v[aa][a]+v[ab][b]+v[ac][c]+v[ad][d]+v[ae][e];
if (sum<=m)
{
    // 状态转移：(a,b,c,d)->(b,c,d,e)
    nd[b][c][d][e]=(nd[b][c][d][e]+cnt)%mod;
}

再是初始化：对于长度为 4 的数，所有符合奇偶位要求的组合都合法（因为不需要检查 5 个连续数位）

最后滚动数组优化空间

具体迭代过程:

for (int l = 4; l < n; ++l)
{
        int nd[5][5][5][5] = {0};//新状态存储数组,作临时存储新状态和状态转移的载体以及滚动更新作用
        int res = l + 1; //新增数位的位置
        int ae = 1 - (res % 2); //新增数位的取值类型

        for (int a = 0; a < 5; ++a) {
            for (int b = 0; b < 5; ++b) {
                for (int c = 0; c < 5; ++c) {
                    for (int d = 0; d < 5; ++d) {
                        int cnt = dp[a][b][c][d];
                        if (cnt == 0) continue;
                        int resa = l - 3, aa = 1 - (resa % 2);
                        int resb = l - 2, ab = 1 - (resb % 2);
                        int resc = l - 1, ac = 1 - (resc % 2);
                        int resd = l, ad = 1 - (resd % 2);

                        for (int e = 0; e < 5; ++e) {
                            int sum = v[aa][a] + v[ab][b] + v[ac][c] + v[ad][d] + v[ae][e];
                            if (sum > m) continue;
                            nd[b][c][d][e] = (nd[b][c][d][e] + cnt) % mod;
                        }
                    }
                }
            }
        }
        memcpy(dp, nd, sizeof(dp));
    }

其他包括四维 dp 的初始化及输出便不展示了。

总结

没文笔不想写了。

End