【DP】Codeforces837D. Round Subset

鉴于我拙劣的DP技术每一道DP题都十分艰难，现下都先记录下来。 [题面](http://codeforces.com/contest/837/problem/D) 题意：从n个数中选取k个，将k个数相乘，乘积末尾的0数目最多有几个； 思路： 每个末尾的0一定是由2*5产生的，那么k个数的乘积中有几对2和5的因子，末尾就有几个0。尽可能使2，5的组合更多。这个连我都想到了是吧！ 比赛的时候用了贪心的想法，先把n个数中共有几对2*5算出来，然后，不断舍去对答案影响最小的数，直到剩下k个数。问题是，遇到 11 2 256 2 2 2 2 2 2 2 2 625 5 这样的数据时，程序豪爽地把256先舍掉了，最后选了2和625. 所以正解当然是用DP； dp[i][k][j] = max_num2 表示从前i个书中取j个，其中有k个因子5时，最多有几个因子2； i因为数组开不下省略了。 转移方程 #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; typedef long long ll; int n, k; ll a[210]; int num2[210] = { 0 }; int num5[210] = { 0 }; int vis[210] = { 0 }; struct node{ int num2, num5; }; int dp[210 * 64][210]; void apart(ll x, int i){ while (x % 2 == 0) num2[i]++, x /= 2; while (x % 5 == 0) num5[i]++, x /= 5; } int main(){ //初始化为负数 memset(dp, 0x80, sizeof(dp)); dp[0][0] = 0; //input int tot = 0; scanf("%d%d", &n, &k); for (int i = 1; i <= n; i++){ scanf("%I64d", &a[i]); apart(a[i], i); } //start DP for (int i = 1; i <= n; i++){ tot += num5[i]; //tot表示因子5的总数 for (int j = min(i, k); j >= 1; j--){ for (int k = tot; k >= num5[i]; k--){ dp[k][j] = max(dp[k][j], dp[k - num5[i]][j - 1] + num2[i]); //取/不取第i个，有点像背包 } } } int ans = 0; for (int i = 1; i <= tot; i++){ ans = max(ans, min(i, dp[i][k])); //i=因子5的数量，dp[i][k] 表示取k个数m，有I个因子5时，有几个因子2 } printf("%d\n", ans); return 0; }