[01背包变形]837 D. Round Subset
题目
题目链接
题意
我们把一个数的 roundness 值定义为它末尾 0 的个数。
给你一个长度为 n 的数列，要求你从中选出 k 个数，使得这些选出的数的积的 roundness 值最大。也就是求
m
a
x
{
m
i
n
(
∑
c
n
t
2
,
∑
c
n
t
5
)
}
max\{min(\sum{cnt_2},\sum{cnt_5})\}
max{min(∑cnt2?,∑cnt5?)}
思路
末尾0的个数那就要统计2和5的个数，先预处理每个数能贡献多少2和5
选K个数容易想到01背包，接下来思考动态规划部分
原问题：一个长度为 n 的数列，要求你从中选出 k 个数，使得这些选出的数的积的 roundness 值最大。
子问题：一个长度为i的数列，要求你从中选出 j 个数，使得这些选出的数的积的 roundness 值最大。
尝试列出转移方程,令
f
[
i
]
[
j
]
f[i][j]
f[i][j]为答案数组，
t
w
o
[
i
]
为
第
i
个
数
因
子
2
数
量
two[i]为第i个数因子2数量
two[i]为第i个数因子2数量,
f
i
v
e
[
i
]
为
第
i
个
数
因
子
5
数
量
five[i]为第i个数因子5数量
five[i]为第i个数因子5数量
不
选
当
前
数
f
[
i
]
[
j
]
=
f
[
i
?
1
]
[
j
]
不选当前数f[i][j]=f[i-1][j]
不选当前数f[i][j]=f[i?1][j]
选
当
前
数
f
[
i
]
[
j
]
=
f
[
i
?
1
]
[
j
?
1
]
+
(
t
w
o
[
i
]
,
f
i
v
e
[
i
]
)
选当前数f[i][j]=f[i-1][j-1]+(two[i],five[i])
选当前数f[i][j]=f[i?1][j?1]+(two[i],five[i])发现写不出来
为什么写不出状态转移方程？
思考一下历史状态信息+当前第i个物品的信息能不能推出新状态的信息
历史信息：
f
[
i
?
1
]
[
j
?
1
]
f[i-1][j-1]
f[i?1][j?1]
告诉你状态
(
i
,
j
)
(i,j)
(i,j)下，
m
i
n
(
c
n
t
2
,
c
n
t
5
)
=
f
[
i
?
1
]
[
j
?
1
]
min(cnt_2,cnt_5)=f[i-1][j-1]
min(cnt2?,cnt5?)=f[i?1][j?1]
新加入物品信息：
t
w
o
[
i
]
,
f
i
v
e
[
i
]
two[i],five[i]
two[i],five[i]
告诉你新加入物品会使得
c
n
t
2
+
t
w
o
[
i
]
cnt_2+two[i]
cnt2?+two[i]以及
c
n
t
5
+
f
i
v
e
[
i
]
cnt_5+five[i]
cnt5?+five[i]
但是我们现在只知道
m
i
n
(
c
n
t
2
,
c
n
t
5
)
min(cnt_2,cnt_5)
min(cnt2?,cnt5?),我们没法通过新加入物品的信息得到
m
i
n
(
c
n
t
2
+
t
w
o
[
i
]
,
c
n
t
5
+
f
i
v
e
[
i
]
)
min(cnt_2+two[i],cnt_5+five[i])
min(cnt2?+two[i],cnt5?+five[i])
那么这种情况我们要考虑维护新的信息
考虑维护新的信息
如果我们知道每个状态的
c
n
t
2
和
c
n
t
5
cnt_2和cnt_5
cnt2?和cnt5?那我们就可以很容易的推出新状态了，我们添加两个维度用来记录
c
n
t
2
和
c
n
t
5
cnt_2和cnt_5
cnt2?和cnt5?
可以得到选第i个物品的状态转移
f
[
i
]
[
j
]
[
p
]
[
q
]
=
f
[
i
]
[
j
]
[
p
?
t
w
o
[
i
]
]
[
q
?
f
i
v
e
[
i
]
]
+
m
i
n
(
p
,
q
)
f[i][j][p][q]=f[i][j][p-two[i]][q-five[i]]+min(p,q)
f[i][j][p][q]=f[i][j][p?two[i]][q?five[i]]+min(p,q)
但是考虑p和q范围，1<=ai<=1e18，单个数two[i]上限为60左右，five[i]上限为26左右，这有200个数，时空双爆炸，螺旋升天。
考虑可不可以把其中一个维度扔出来作为dp的含义
尝试把
c
n
t
2
cnt_2
cnt2?扔出来作为dp的含义
g
[
i
]
[
j
]
[
p
]
g[i][j][p]
g[i][j][p]表示前i个中选j个且他们的积有p个因子5的情况下，最多可以有多少个2
状态转移方式
不选第i个
g
[
i
]
[
j
]
[
p
]
=
g
[
i
?
1
]
[
j
]
[
p
]
g[i][j][p]=g[i-1][j][p]
g[i][j][p]=g[i?1][j][p]
选第i个
g
[
i
]
[
j
]
[
p
]
=
m
a
x
(
g
[
i
]
[
j
]
[
p
]
,
g
[
i
?
1
]
[
j
?
1
]
[
p
?
f
i
v
e
[
i
]
]
+
t
w
o
[
i
]
)
g[i][j][p]=max(g[i][j][p],g[i-1][j-1][p-five[i]]+two[i])
g[i][j][p]=max(g[i][j][p],g[i?1][j?1][p?five[i]]+two[i])
初始值：默认为负无穷，g[1][0][0]=0(因为这题恰好）
最后遍历一遍取max{min(p,q)}就行了
进步优化可以压掉第一个维度，类似01背包压掉一维度
代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
int n,m,ans,tmp;
int a[210],cnt2[210],cnt5[210];
int dp[210][20000];
//设dp[i][j]表示选i个物品,5有j个时2的最多数量。
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
tmp=a[i];
while(tmp%2==0)
cnt2[i]++,tmp/=2;
while(tmp%5==0)
cnt5[i]++,tmp/=5;
}
memset(dp,0xcf,sizeof(dp));
dp[0][0]=0;
for(int i=1;i<=n;i++)
for(int j=m;j>=1;j--)
for(int k=10000;k>=cnt5[i];k--)
dp[j][k]=max(dp[j][k],dp[j-1][k-cnt5[i]]+cnt2[i]);
for(int i=0;i<=10000;i++)
ans=max(ans,min(i,dp[m][i]));
printf("%lld",ans);
return 0;
}