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

chao_tao2 · 2026-04-22 18:46:12 · 题解

题目分析

想要在 6 进制的情况下末尾的 0 最多，就要让质因数中的 2 和 3 尽可能的多，所以我们可以先处理一下所有数字质因数中的 2 和 3 的数量并存起来。

然后就可以用 dp 了，但是直接用会 MLE，所以我们可以把 dp 的定义改成：f_{i,j} 表示已经选了 i 个数，质因数 2 的最大数量为 j 时，质因数 3 的最大数量。

最后求一下最大值就行了。

#include <bits/stdc++.h>
using namespace std;
const int N = 205;
const int M = 1005;
int f[N][M];
int cnt2[N],cnt3[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,k;
    cin >> n >> k;
    for (int i = 1;i <= n;i++){
        int x;
        cin >> x;
        int a = 0,b = 0;
        while (x % 2 == 0){
            x /= 2;
            a++;
        }
        while (x % 3 == 0){
            x /= 3;
            b++;
        }
        cnt2[i] = a;
        cnt3[i] = b;
    }
    memset(f,-1,sizeof(f));
    f[0][0] = 0;
    for (int i = 1;i <= n;i++){
        for (int j = k;j >= 1;j--){
            for (int k1 = M - 1;k1 >= cnt2[i];k1--){
                if (f[j - 1][k1 - cnt2[i]] >= 0) f[j][k1] = max(f[j][k1],f[j - 1][k1 - cnt2[i]] + cnt3[i]);
            }
        }
    }
    int maxn = 0;
    for (int i = 0;i < M;i++){
        if (f[k][i] >= 0) maxn = max(maxn,min(i,f[k][i]));
    }
    cout << maxn;
    return 0;
}