Codeforces 837D–Round Subset （DP）

原题链接：http://codeforces.com/contest/837/problem/D

题意：在n个数字中，取k个数，使这些数的乘积后缀“0”的个数最大，输出后缀0的最大数量。

思路：显然只有含有因子2和5的数相乘才能得到10的倍数，所以对每个数求因子2和5的个数。

这里运用背包的思想，对于 i 个数，假设总共有 j 个2因子数目，能够得到的5的因子数目最大为dp[i][[j]，状态转移方程为：

dp[i][j]=max(dp[i][j], dp[i-1][dp[j-num_two]+num_five])

其中num_two和num_five是枚举到的某个数所含2和5的因子数。

最后求出min(i, dp[i][j])的最大值即可。

AC代码：

 #include<iostream>
 #include<cstring>
 #include<cstdio>
 #include<vector>
 using namespace std;
 const int MAXN=;
 const int INF=;
 int dp[MAXN][MAXN*];
 int main()
 {
     int n,k;
     long long a;
     scanf("%d %d", &n, &k);
     int sum2=;
     for(int i=;i<MAXN;i++){
         for(int j=;j<MAXN*;j++)
             dp[i][j]=-INF;
     }
     dp[][]=;
     for(int s=;s<=n;s++){
         scanf("%I64d", &a);
         int x=,y=;
         while(a%==){
             a/=;
             x++;
         }
         while(a%==){
             a/=;
             y++;
         }
         sum2+=x;
         for(int i=min(s, k);i>=;i--){//避免重复计算导致答案错误，从大到小
             for(int j=x;j<=sum2;j++){
                 dp[i][j]=max(dp[i-][j-x]+y, dp[i][j]);
             }
         }
     }
     int res=,tmp;
     for(int j=;j<=sum2;j++){
         tmp=min(j, dp[k][j]);
         res=max(tmp, res);
     }
     printf("%d\n", res);
     return ;
 }