首页 > 代码库 > Educational Codeforces Round 26 D dp,思维
Educational Codeforces Round 26 D dp,思维
Educational Codeforces Round 26
D. Round Subset
题意：有 n 个数，从中选出 k 个数，要使这 k 个数的乘积末尾的 0 的数量最多。
tags：dp好题
dp[i][j][l] 表示前 i 个数，选取了其中 j 个数，分解因子后有 l 个 5时，最多有多少个 2 。i 这一维明显可以省略。
这题一开始有个地方写挫了。。选取 j 个数时，应该反着来，即 for( j, k, 1) ，不是 for( j, 1, k) ，不然会多算。
#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define rep(i,a,b) for (int i=a; i<=b; ++i)#define per(i,b,a) for (int i=b; i>=a; --i)#define mes(a,b) memset(a,b,sizeof(a))#define INF 0x3f3f3f3f#define MP make_pair#define PB push_back#define fi first#define se secondtypedef long long ll;const int N = 200005;int dp[210][6100], n, k;int main(){ scanf("%d%d", &n, &k); ll ai, a2, ans=0; int t2, t5; rep(j,0,200) rep(l,0,6000) dp[j][l] = -INF; dp[0][0] = 0; rep(i,1,n) { scanf("%lld", &ai); t2 = t5 = 0; for(a2=ai; a2%2==0; a2/=2, ++t2) ; for(a2=ai; a2%5==0; a2/=5, ++t5) ; per(j,k,1) //???? { rep(l,t5,6000) { dp[j][l] = max(dp[j][l], dp[j-1][l-t5]+t2); if(j==k) ans = max(ans, 1LL*min(l, dp[j][l])); } } } printf("%lld\n", ans); return 0;}
Educational Codeforces Round 26 D dp,思维
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。