首页 > 代码库 > 【动态规划】【滚动数组】Educational Codeforces Round 26 D. Round Subset

【动态规划】【滚动数组】Educational Codeforces Round 26 D. Round Subset

 给你n个数,让你任选K个,使得它们乘起来以后结尾的0最多。

将每个数的因子2和因子5的数量求出来,记作a[i]和b[i]。

答案就是max{ min{Σa[i],Σb[i]} }(a[i],b[i]是选择的那些数)。

暴力dp是f(i,j,k)表示前i个数,选j个,其中包含k个5的情况下,最多能包含多少个2。

转移是f(i,j,k)=max{ {f(t,j-1,k-b[i]}+a[i]}(1<=i<t) , f(i-1,j,k) },时间是O(18 * n^3),但空间存不下。

注意第二维为j时,只会从j-1或者j转移过来,所以可以滚动数组优化。

【动态规划】【滚动数组】Educational Codeforces Round 26 D. Round Subset