cf837D(01背包)

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

题意: 给出 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); //注意判断上一种状态是否存在

代码:

 #include <iostream>

 #include <string.h>

 #include <math.h>

 #define ll long long

 using namespace std;

 const int MAXN = 2e2 + ;

 const int MAX = 6e3;

 struct node{

     int x, y;

 }gel[MAXN];

 int dp[MAXN][MAX];

 int main(void){

     ll x;

     int n, k, cnt = ;

     cin >> n >> k;

     for(int i = ; i <= n; i++){

         cin >> x;

         while(x %  == ){

             gel[i].x += ;

             x /= ;

         }

         while(x %  == ){

             gel[i].y += ;

             x /= ;

             cnt++;

         }

     }

     memset(dp, -, sizeof(dp));

     dp[][] = ;

     for(int i = ; i <= n; i++){

         for(int j = k; j >= ; j--){

             for(int l = gel[i].y; l <= cnt; l++){

                 if(dp[j - ][l - gel[i].y] != -) dp[j][l] = max(dp[j][l], dp[j - ][l - gel[i].y] + gel[i].x);

             }

         }

     }

     int sol = ;

     for(int i = ; i <= MAX; i++){

         sol = max(sol, min(i, dp[k][i]));

     }

     cout << sol << endl;

     return ;

 }

巴特西

cf837D(01背包)

最新文章

热门文章