首页 > 代码库 > [CF837D] Round Subset（滚动数组，01背包）

[CF837D] Round Subset（滚动数组，01背包）

2024-11-19 19:58:38   203人阅读

题目链接：http://codeforces.com/contest/837/problem/D

题意：n个数里选k个数，使得它们的乘积末尾0个数最多。

只需要统计每个数的2和5的数量，一个作为容量，一个作为价值。f(i,k,j)表示前i个数选k个，一共有j个2的时候，5最多有几个。

外层枚举前i个数，内层做01背包就可以。但是会MLE，所以滚动数组。

特别注意的是，滚动数组在滚动的时候要拷贝整层，原因是我在更新01背包的时候没有及时复制。。。

还有f要注意当前层一定要从之前存在的状态更新过来，否则状态就不对了。顺便，用map写就太麻烦了。。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 const int maxn = 202;
 6 const int maxm = 63*maxn;
 7 int n, K;
 8 int f[2][maxn][maxm];
 9 int w2[maxn], w5[maxn], tot[maxn];
10 
11 signed main() {
12     // freopen("in", "r", stdin);
13     LL a;
14     while(~scanf("%d%d",&n,&K)) {
15         memset(f, -1, sizeof(f));
16         memset(tot, 0, sizeof(tot));
17         memset(w2, 0, sizeof(w2));
18         memset(w5, 0, sizeof(w5));
19         for(int i = 1; i <= n; i++) {
20             scanf("%lld", &a);
21             while(a % 5 == 0) w5[i]++, a /= 5;
22             while(a % 2 == 0) w2[i]++, a /= 2;
23             tot[i] = tot[i-1] + w2[i];
24         }
25         f[0][0][0] = 0;
26         int ret = 0;
27         for(int i = 1; i <= n; i++) {
28             for(int k = 1; k <= K; k++) {
29                 for(int j = tot[i]; j >= w2[i]; j--) {
30                     f[1][k][j] = max(f[1][k][j], f[0][k][j]);
31                     if(f[0][k-1][j-w2[i]] != -1) {
32                         f[1][k][j] = max(f[0][k-1][j-w2[i]]+w5[i], f[1][k][j]);
33                     }
34                     ret = max(ret, min(j, f[1][k][j]));
35                 }
36             }
37             for(int k = 1; k <= K; k++) {
38                 for(int j = maxm-1; j >= 0; j--) {
39                     f[0][k][j] = f[1][k][j];
40                 }
41             }
42         }
43         printf("%d\n", ret);
44     }
45     return 0;
46 }

 

[CF837D] Round Subset（滚动数组，01背包）


联系
我们