题解：B4515 [四川青少年 C++ 算法设计大赛 2025] 圆度

Zelda_max · 2026-04-19 21:19:35 · 题解

先说本题的核心理论：

如果一个六进制数末尾有 0，这个数就能被 6 整除，而且 0 越多，这个数就能被 6 的更高次幂给整除。

举个例子，如 (1100)_6，这个数等价于 (252)_{10}，而 (252)_{10} 这个数能被 36 即 6^2 整除，验证了上面的理论。

所以我们要尽可能拿有因子 6 即有因子 2 和 3 的数。而最大化利益，你能联想到什么算法——当然是 DP 了。

我们只要先将 a_1,a_2\dots,a_n 分解，记录这些数因子 2 和因子 3 的个数，再用 DP 找出最优解就行了。

我们可以设计 dp_{j,k} 为表示已经选了 j 个数，这些数共有 k 个因子 2 的情况下所能获得的因子 3 的最大个数，以下为状态转移方程（i 为当前的物品）：

::::success[AC 代码]

#include<bits/stdc++.h>
using namespace std;
int a2[201], a3[201];
int dp[201][1001];
int main() {
    int n, k, ans = 0;
    scanf("%d%d", &n, &k);
    for(int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        while(x % 2 == 0) {
            a2[i]++;
            x /= 2;
        }
        while(x % 3 == 0) {
            a3[i]++;
            x /= 3;
        }
//      a2[i] 用来存储 a[i] 的因子 2 的个数，a3[i] 用来存储 a[i] 的因子 3 的因子 3 的个数。
    }
//  初始化，不要跟我一样初始化成INT_MIN，会WA
    memset(dp, -0x3f, sizeof dp);
    dp[0][0] = 0;
/*
    将任意的 for 循环调换
    或如把：for(int j = k; j >= 1; j--) ->
    for(int j = 1; j <= k; j++) 都会WA
*/
    for(int i = 1; i <= n; i++) {
//      枚举每一个数
        for(int j = k; j >= 1; j--) {
            for(int l = 1000; l >= a2[i]; l--) {
//              枚举可能的因数 2 的数量
                dp[j][l] = max(dp[j][l], dp[j-1][l-a2[i]] + a3[i]);
//              类似01背包的状态转移方程
                if(j == k) ans = max(min(dp[j][l], l), ans);
//              在选了 k 个数（第二层循环）后在因数 2 的个数和因数 3 的个数中取更小值
            }
        }
    }
    printf("%d", ans);
    return 0;
}

::::