选数（01背包）

选数

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

题意

给你 n n n个整数 a 1 a 2 , . . . , a n a_1a_2,...,a_n a1a2,...,an，让你从中选恰好 k k k个，使得选出的数的乘积的末位的 0 0 0的数量尽可能多，输出末位 0 0 0的最大可能量。

题解

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

Code

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include  
#include 
#include 
#include  
#include 
#define x first
#define y second
#define debug(x) cout<<#x<<":"< PII;
typedef pair 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;
}

选数（01背包）

C/C++/C#相关栏目本月热门文章