Codeforces 837 D Round Subset DP 思维

　　题目链接： 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 <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iterator>
#include <cmath>
#include <algorithm>
#include <stack>
#include <deque>
#include <map>
#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

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