CF837 D.Round Subset【背包DP】

题目链接：codeforces 837D)

题解

要求结果的 最多，不难想到这个数的因子 和 的个数尽可能多。故将每个数分解，然后就是一个比较简单的背包问题。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 220;
int cnt2[N], cnt5[N];
int dp[N][5010]; // 前i个数，有j个5（也可以计2的个数，不过空间大点）能得到的最多的2的个数
void get2(ll num, int pos) {
    while (num % 2 == 0) {
        cnt2[pos]++;
        num /= 2;
    }
}
void get5(ll num, int pos) {
    while (num % 5 == 0) {
        cnt5[pos]++;
        num /= 5;
    }
}
int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        ll num; cin >> num;
        get2(num, i);
        get5(num, i);
    }
    memset(dp, -0x3f, sizeof(dp));
    int ans = 0;
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = k; j >= 1; j--) {
            for (int l = cnt5[i]; l <= 5000; l++) {
                dp[j][l] = max(dp[j][l], dp[j-1][l-cnt5[i]] + cnt2[i]);
            }
        }
    }
    for (int i = 1; i <= 5000; i++) {
        ans = max(ans, min(i, dp[k][i])); // 取最多的2和5的状态
    }
    cout << ans << endl;
    return 0;
}