首页 > 代码库 > 【动态规划】【滚动数组】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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。