Codeforces 837 D Round Subset DP 思维-白红宇

Codeforces 837 D Round Subset DP 思维

阅读量：7106 次

发布时间：2019-06-28

本文共 1796 字，大约阅读时间需要 5 分钟。

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

　　题目大意：给你一个n, k，让你从一个大小为n的几个中选出k个数，是他们乘积的0最多

　　解题思路：可以素数分解一下，两个数0的个数就是min(2的个数， 5的个数)，这样我们就只需要从n个(n2, n5)点对中选取K个，使他加和最大就可以了， DP

　　　　三个状态分别应该是dp(i, j, k)前j个数，选取了j个， 2的个数为k的最大5的个数，很像背包了对吧

　　　　状态转移方程就是: dp(i, j, k) = max(dp(i-1, j-1, k-n2)+n5, dp(i-1, j, k))

　　　　本来需要三维的，但是第二维肯定是又j-1 ----> j所以滚动数组求解即可

　　代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #define lson l, m, rt<<1#define rson m+1, r, rt<<1|1#define mem0(a) memset(a,0,sizeof(a))#define meminf(a) memset(a,-0x3f,sizeof(a))typedef long long ll;using namespace std;const int INF = 0x3fffffff;const int maxn = 205;const int maxm = 205*64;int dp[maxn][maxm]; // dp(i, j)表示前i 个数中有了j个2时候5的最多个数int n, k;ll in[maxn];int a[maxn];int b[maxn];void fun(int i, ll num) { int cnt = 0; while( num % 2 == 0 ) { num /= 2; cnt++; } a[i] = cnt; cnt = 0; while( num % 5 == 0 ) { num /= 5; cnt++; } b[i] = cnt;}int main() { cin >> n >> k; for( int i = 0; i < n; i++ ) { cin >> in[i]; fun(i, in[i]); }// cout << "====" << endl; for( int i = 0; i <= k; i++ ) { for( int j = 1; j <= maxm; j++ ) { dp[i][j] = -INF; } } dp[0][0] = 0; for( int i = 0; i < n; i++ ) { for( int j = k; j >= 1; j-- ) { for( int l = a[i]; l < maxm; l++ ) { dp[j][l] = max( dp[j][l], dp[j-1][l-a[i]]+b[i] ); } } } int ans = 0; for( int i = 0; i <= maxm; i++ ) { ans = max( ans, min(i,dp[k][i]) ); } cout << ans << endl; return 0;}

View Code

　　思考：遇到一个非常无解的BUG，循环的时候如果判等于maxm就wa， < 就A，我就非常非常不解，然后这道题没有想出来，哎，通过这道题也知道了遇到0的问题就想到素数分解成2， 5

　　我傻逼啊.........加上等于号数组不就是越界了吗.......

转载于:https://www.cnblogs.com/FriskyPuppy/p/7367756.html

你可能感兴趣的文章

HDU 4836 The Query on the Tree lca || 欧拉序列 || 动态树