[数据结构与算法]选数 （转化为二维费用背包问题

4081. 选数
题意：
给定 $n$ 个数，选出恰好 $k$ 个数使得这些数的乘积末尾 $0$ 的个数最多，求最多 $0$ 的个数
思路：
有限制的选择问题，即为背包问题
$10$ 质因子分解后为 $2$ 和 $5$，我们只需要考虑选出来的数中 $2$ 和 $5$ 的数量，答案即为 $min(cn{t}_2,cn{t}_5)$
这里有一个技巧，就是将 $2$ 或 $5$ 的个数当作背包容量
假设把 $5$ 的个数当作背包容量，$2$ 的个数当作价值，那么就可以转化成：当选的数中有 $1$ 个 $5$ 的情况下，最多能选出多少个 $2$…
注意这里最好选择 $5$ 的个数为背包容量，因为 $a_i<=10^{18}$，一个数最多包含 $25$ 个 $5$，那么 $200$ 个数最多包含 $5000$ 个 $5$，如果选择 $2$ ，那么包含 $2$ 的个数会更多，时间复杂度和空间复杂度都更大
此外还有一个限制就是必须恰好选 $k$ 个数
我们可以把每个数的体积当成 $1$，然后通过加一维费用来约束这个条件
至此，这个问题就转化为了二维费用背包问题
最后需要枚举选了多少个 $5$，然后和 $2$ 的个数取 $min$ 维护答案即可
code：

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define ld long double
#define all(x) x.begin(), x.end()
#define eps 1e-6
using namespace std;
const int maxn = 2e6 + 9;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m;
int f[209][5009];
int w[209], v[209];

void work()
{
	cin >> n >> m;
	for(int i = 1; i <= n; ++i){
		ll x;cin >> x;
		while(x && x % 5 == 0) v[i]++, x /= 5;
		while(x && x % 2 == 0) w[i]++, x /= 2;
	}
	memset(f, -0x3f, sizeof(f));
	f[0][0] = 0;
	for(int i = 1; i <= n; ++i)
		for(int j = m; j >= 1; --j)
			for(int k = 5000; k >= v[i]; --k)
				f[j][k] = max(f[j][k], f[j-1][k-v[i]] + w[i]);
	int ans = 0;
	for(int i = 1; i <= 5000; ++i)
		ans = max(ans, min(i, f[m][i]));
	cout << ans;
}

int main()
{
	ios::sync_with_stdio(0);
//	int TT;cin>>TT;while(TT--)
	work();
	return 0;
}