Codeforces-837D Round Subset 题解

题目链接

题面

我们把10进制下数末尾0的个数称为这个数的圆度。比如100010的圆度就是1。

给你一个长度为nn的正整数数组，你要选择恰好kk个数的子集，使这些数的乘积的圆度尽可能大。

1≤n≤2001 \leq n \leq 200

1≤k≤n1 \leq k \leq n

1≤ai≤10181 \leq a_i \leq 10^{18}

不开long long见祖宗！别忘了！

思路

众所周知，一个数末尾的00一定是由好几个1010相乘得到的，而1010只能分成22和55相乘，所以我们如果想知道一个数末尾的00有多少个，就是minmin(这个数因子22的个数,这个数因子55的个数)

所以再看看这个数据范围，暴力是出不了奇迹了，所以最优的办法就是考虑一下DP。

我们定义状态：dp[i][j]dp[i][j]表示前ii个数里有jj个55时可以得出来最多22的个数。（当然你想要存22也不是不行，不过这样更节省空间，毕竟不是比赛，写更好的代码吧）

所以按照这个状态，我们最后枚举一遍可能含有的5的个数，可以得到的答案就是min(i,dp[k][i])min(i,dp[k][i])。

差点忘了转移了，实际上它很像一个背包问题，就是这个数选与不选的问题。

我们ii表示当前的数，jj选的数量，kk表示5的因子个数，表示所以转移方程就应该是这个：dp[j][k]=max(dp[j][k],dp[j−1][k−count5[i]]+count2[i])dp[j][k]=max(dp[j][k],dp[j-1][k-count5[i]]+count2[i])。

现在思路都梳理清楚啦，开始写代码吧！

代码

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 220;
int cnt2[222], cnt5[222];
int dp[222][5555];
signed main()
{
	int n, k;
	cin >> n >> k;
	memset(dp, -0x3f, sizeof(dp)); //没访问到初始化为无穷小
	dp[0][0] = 0; //初始化记得
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		while (x % 2 == 0) {
			x /= 2;
			cnt2[i]++;
		}
		while (x % 5 == 0) {
			x /= 5;
			cnt5[i]++;
		}
		//这里我们直接对x进行操作是因为分离因子的时候我们用的2,5都是质因子，是不会有影响的
		//我们不用记录数是因为我们只关心2,5的个数，存在数组就可以了
	}
	for (int i = 1; i <= n; i++) {
		for (int j = k; j >= 1; j--) {
			for (int l = cnt5[i]; l <= 5000; l++) { //这里k会重名所以我们用l代替
				dp[j][l] = max(dp[j][l], dp[j - 1][l - cnt5[i]] + cnt2[i]);
			}
		}
	}
	int ans = 0; // 这里我以前打了个-1145141919810 结果WA了才发现答案可能为0 说出来让你开心开心
	for (int i = 1; i <= 5000; i++) {
		ans = max(ans, min(i, dp[k][i]));// 题目让求最大了
	}
	cout << ans;
	return 0;
}

感谢你看完了

GOODBYE