题目链接:

 

题意: 给出 n 个数, 从中选出 k 个数使得这 k 个数的乘积末尾 0 最多 .

 

思路: 先记录每个数能分解出的 2 和 5 的数目, 然后弄个01背包即可 .

用 dp[i][j][l] 表示从前 i 个数中选出 j 的数其中 5 的个数为 l 个的情况下 2 的数目最多是多少 .

初始状态为 dp[0][0][0] = 0, 推到终态 dp[n][k][MAX] 即可 . 注意要存在上一种状态才能到达下一种状态 .

然而开三维会 mle, 可以优化一下空间, 去掉 i 这维 .

状态转移方程式: if(dp[j - 1][l - gel[i].y] != -1) dp[j][l] = max(dp[j][l], dp[j - 1][l - gel[i].y] + gel[i].x); //注意判断上一种状态是否存在

 

代码:

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #define ll long long 5 using namespace std; 6  7 const int MAXN = 2e2 + 5; 8 const int MAX = 6e3; 9 struct node{10     int x, y;11 }gel[MAXN];12 13 int dp[MAXN][MAX];14 15 int main(void){16     ll x;17     int n, k, cnt = 0;18     cin >> n >> k;19     for(int i = 1; i <= n; i++){20         cin >> x;21         while(x % 2 == 0){22             gel[i].x += 1;23             x /= 2;24         }25         while(x % 5 == 0){26             gel[i].y += 1;27             x /= 5;28             cnt++;29         }30     }31     memset(dp, -1, sizeof(dp));32     dp[0][0] = 0;33     for(int i = 1; i <= n; i++){34         for(int j = k; j >= 1; j--){35             for(int l = gel[i].y; l <= cnt; l++){36                 if(dp[j - 1][l - gel[i].y] != -1) dp[j][l] = max(dp[j][l], dp[j - 1][l - gel[i].y] + gel[i].x);37             }38         }39     }40     int sol = 0;41     for(int i = 1; i <= MAX; i++){42         sol = max(sol, min(i, dp[k][i]));43     }44     cout << sol << endl;45     return 0;46 }