hihoCoder 1706 最大化末尾连续0的个数

算法 hihoCoder

题目

题目地址：hihoCoder 1706

题目大意：
从$N$个正整数里面选出$M$个整数, 使它们的乘积末尾有最多的$0$

分析

由于是正整数, 只有$2$和$5$的乘积会产生$0$, 每有一对$(5,2)$都会产生一个$0$, 故, 只需要统计出相乘整数的$2$和$5$的因子个数即可, 最后末尾$0$的个数为两者的较小值

//value的因子factor的个数
int get_factor(int64_t value, int factor){
    int n = 0;
    while(value !=0 && value%factor==0){
        value /= factor;
        n++;
    }
    return n;
}

现在问题就转化为了在$N$对因子中选取$M$对因子, 使这$M$对因子的$5$的总因子和$2$的总因子的较小值最大, 转换成了一个搜索问题

有三种方法解决这个问题

方法一：暴力搜

这是最容易想到的一个方法，我对动态规划的设定状态空间还不是很熟悉，所以最开始想到的是用递归的方法暴力搜，但会超时（TLE）

一共选择$M$个数据，每次选择的数据不同，用一个used[MAXSIZE]数组标记该数据是否被选取，该递归搜索树的深度为$M$层

int search(int m, int f_2, int f_5){
    if(m==M){
        return min(f_2, f_5);
    }
    int c_m = 0;
    for(int i=0; i<N; i++){
        if(!used[i]){
            used[i] = true;
            int t = search(m+1, f_2+factors_2[i], f_5+factors_5[i]);
            used[i] = false;
            c_m = max(t, c_m);
        }
    }
    return c_m;
}
cout<<search(0, 0, 0)<<endl;

方法二：先排序，后选择

这个方法是第二个想到的方法，分别按照因子2和因子5的个数进行排序，每个排序两次，分别得到因子2优先一个和因子5优先一个，最后根据这两个排序结果从中抽选出不同的M个数。选择的该数只能是resort_2或resort_5各自数组中最大那个（数组的首个未被选取的元素），并且要使得min(total_2+f_2, total_5+f_5)最大。

但这种方法报了个Wrong Answer，还没想到是为什么，但神说这种方法是贪心的，肯定不对。。。

int resort_2[MAXSIZE];
int resort_5[MAXSIZE];
void swap(int L[], int a, int b){
    int t = L[a];
    L[a] = L[b];
    L[b] = t;
}
int resort_2[MAXSIZE];
int resort_5[MAXSIZE];
void m_sort(int factors[], bool (*cmp)(int, int), int indexs[]){
    for(int i=0; i<N; i++){
        for(int j=i+1; j<N; j++){
            if(cmp(factors[indexs[i]], factors[indexs[j]])){
                swap(indexs, i,j);
            }
        }
    }
}
bool cmp_1(int a, int b){
    return a<b;
}
//Wrong Answer了。。。
int sort_solve(){
    for(int i=0; i<N; i++){
        resort_2[i] = i;
        resort_5[i] = i;
    }
    m_sort(factors_5, cmp_1, resort_2);
    m_sort(factors_2, cmp_1, resort_2);
    m_sort(factors_2, cmp_1, resort_5);
    m_sort(factors_5, cmp_1, resort_5);
    int i_2 = 0,i_5 = 0;
    int total_2 = 0, total_5 = 0;
    for(int i=0; i<M; i++){
        while(used[resort_2[i_2]]){
            i_2++;
        }
        int total_2_2 = total_2 + factors_2[resort_2[i_2]];
        int total_2_5 = total_5 + factors_5[resort_2[i_2]];
        while(used[resort_5[i_5]]){
            i_5++;
        }
        int total_5_5 = total_5 + factors_5[resort_5[i_5]];
        int total_5_2 = total_2 + factors_2[resort_5[i_5]];
        if(min(total_2_2, total_2_5) > min(total_5_2, total_5_5)){
            used[resort_2[i_2]] = true;
            total_2 = total_2_2;
            total_5 = total_2_5;
        }else{
            used[resort_5[i_5]] = true;
            total_2 = total_5_2;
            total_5 = total_5_5;
        }
    }
    return min(total_2, total_5);
}
cout<<sort_solve()<<endl;

方法三：动态规划

这个方法是同学告诉我的，我刚开始刷题，有点不会写多组的动态规划，状态大于两个维度就不会分析了。。。

他用了一个三个维度的状态数组f[i][j][k]，表示从前$i$个元素中选择$j$个元素，并且当前总共有$k$个$5$时最大的连续$0$的个数，他这样设置状态数组巧妙的地方在于f[i][j][k]中的$k$直接就包含了，如果要选择第$i$个元素，该选择该数导致的结果是增加了该数的$5$因子数和$2$因子数的最小值

则状态转换公式为：

f[i][j][k] = max(f[i][j][k],f[i-1][j][k]);
f[i][j][k] = max(f[i][j][k],f[i-1][j-1][k-a5[i]]+a2[i]); if(k>=a5[i] && j>0) 

当前总共选择$j$个：
f[i-1][j] 表示当前不选择$i$
f[i-1][j-1] 表示当前选择$i$

由于末尾连续$0$的个数确定时$2$和$5$的个数是不确定的，只是$2$和$5$个数的极小值，然而下一个状态与$2$和$5$的个数都有关，所以还需要一个状态来表示具体的$2$和$5$的个数

#include <iostream>
#include <string.h>
#include <cstdio>
#include <set>
#include <algorithm>
#include <cmath>
#define maxn 111
using namespace std;
int f[111][111][1300];
int n,m;
int a[maxn];
int a2[maxn];
int a5[maxn];
int main()
{
    int t;
    scanf("%d%d",&n,&m);
    memset(a2,0,sizeof(a2));
    memset(a5,0,sizeof(a5));
    memset(f,-0x3f3f3f3f,sizeof(f));
    f[0][0][0]=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&t);
        while(t%2==0)
        {
            a2[i]++;
            t /= 2;
        }
        while(t%5==0)
        {
            a5[i]++;
            t /= 5;
        }
        for(int j=0;j<=i && j<=m;j++)
            for(int k=0;k<1300;k++)
            {
                f[i][j][k] = max(f[i][j][k],f[i-1][j][k]);
                if(k>=a5[i] && j>0) f[i][j][k] = max(f[i][j][k],f[i-1][j-1][k-a5[i]]+a2[i]);
            }
    }
    int ans = 0;
    for(int i=0;i<1300;i++)
        ans = max(ans,min(f[n][m][i],i));
    printf("%d\n",ans);
    return 0;
}

code：zsh965866221/CodePractice