[数据结构与算法]选数（01背包）

选数

[Link](4081. 选数 - AcWing题库)

题意

给你$n$个整数$a_1{a}_2,...,a_n$，让你从中选恰好$k$个，使得选出的数的乘积的末位的$0$的数量尽可能多，输出末位$0$的最大可能量。

题解

发现只有$2\times 5$才能产生$0$,其他的任何数相乘都是不会产生$0$的，因此我们可以统计出每一个数含有因子$2$的个数$w[i]$和因子$5$的个数$v[i]$。我们要进行的有限制的选取问题，所以可以用背包来解。对于产生$0$有$2和5$两个因素，因为$5$大一些一个数最多含有$5$的次幂少一些，我们可以少开一点空间，我们把每个数因子$5$的个数当作体积，因子$2$的个数当作价值，状态可表示为$f[i,j,k]=从前i个里恰好选j个且体积为k的最大价值$，按照01背包转移，优化掉第一维。最后枚举一下包含因子$5$的个数，取最大即可，注意最后枚举的时候要在含因子$2$和含因子$5$的个数中取$min$(多的2或5无法和别的作用产生0，没有意义)。

Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <set>
#include <queue>
#include <vector>
#include <map>
#include <bitset>
#include <unordered_map>
#include <cmath> 
#include <stack>
#include <iomanip>
#include <deque> 
#include <sstream>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 205, M = N * 26 , INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
#define tpyeinput int
inline char nc() {static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
inline void read(tpyeinput &sum) {char ch=nc();sum=0;while(!(ch>='0'&&ch<='9')) ch=nc();while(ch>='0'&&ch<='9') sum=(sum<<3)+(sum<<1)+(ch-48),ch=nc();}
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int n, m, k;
int f[N][M];
int v[N], w[N];
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i ++ ) {
		LL t; cin >> t;
		while (t % 5 == 0) v[i] ++, t/=5;
		while (t % 2 == 0) w[i] ++, t/=2;
	}
	memset(f, -0x3f, sizeof f);
	f[0][0] = 0;
	for (int i = 1; i <= n; i ++ ) 
		for (int j = m; j; j -- )
			for (int k = i * 25; k >= v[i]; k -- )
				f[j][k] = max(f[j][k], f[j - 1][k - v[i]] + w[i]);
	int res = 0;
	for (int i = 1; i <= m * 25; i ++ )
		res = max(res, min(i, f[m][i]));
	cout << res << endl;
    return 0;
}