Round Subset - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
先想一想 10 是有何而来？显然 10 只能由 2和5组成
所以我们先预处理出每个数的 2数量和5数量
这道题关键是dp的状态如何设置。
我们令 dp2[i][j][k] 为前i个数 选j个 此时有0个k的情况下，2最多能有几个
dp5[i][j][k] 为前i个数 选j个 此时有0个k的情况下，5最多能有几个
根据题目范围 k至多有 18*200 个
假设现在我们知道了 dp2[i-1][j][k] dp5[i-1][j][k] 的情况, 到了第i个数，第i个数有 x个2,y个5.现在进行dp转移
倘若第i个数不选: dp2[i][j][k]=max(dp2[i][j][k],dp2[i-1][j][k]),dp5[i][j][k]=max(dp5[i][j][k],dp5[i-1][j][k])
倘若第i个数选：
对于dp2[i-1][j][k]：此时 _2的个数:dp2[i-1][j][k]+x, _5的个数:y , 此时能组成_0的个数:min(_2,_5)
所以 dp2[i][j+1][k+_0]=max(dp2[i][j+1][k+_0],_2-_0)
dp5[i][j+1][k+_0]=max(dp5[i][j+1][k+_0],_5-_0)
对于dp5[i-1][j][k]相同处理
预处理:dp2[0][0][0]=dp5[0][0][0]=0,其实都为-1表示不合法的情况
再用滚动数组优化空间即可
Code:
#include<bits/stdc++.h> using namespace std; #define ll long long #define mp make_pair #define pb push_back #define popb pop_back #define fi first #define se second #define popcount __builtin_popcount #define popcountll __builtin_popcountll const int N=210; //const int M=; //const int inf=1e9; //const ll INF=1e18; int T,n,m; int dp2[3][N][19*N],dp5[3][N][19*N]; pair<int,int> v[N]; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; } int main() { // freopen("","r",stdin); // freopen("","w",stdout); // ios::sync_with_stdio(0); // cin.tie(0); n=read(),m=read(); for(int i=1;i<=n;i++) { ll x; scanf("%lld",&x); int _2=0,_5=0; while(x%2==0) _2++,x/=2; while(x%5==0) _5++,x/=5; v[i]=mp(_2,_5); } memset(dp2,-1,sizeof(dp2)); memset(dp5,-1,sizeof(dp5)); dp2[0][0][0]=0,dp5[0][0][0]=0; int ans=0; for(int i=1;i<=n;i++) { for(int j=0;j<=m;j++) for(int k=0;k<=18*N;k++) { if(dp2[(i-1)%2][j][k]!=-1) { ans=max(ans,k); dp2[i%2][j][k]=max(dp2[i%2][j][k],dp2[(i-1)%2][j][k]); int _2=dp2[(i-1)%2][j][k]+v[i].fi,_5=v[i].se; int _0=min(_2,_5); // printf("%d %d %d %d\n",i,j,k,_0); dp2[i%2][j+1][k+_0]=max(dp2[i%2][j+1][k+_0],_2-_0); dp5[i%2][j+1][k+_0]=max(dp5[i%2][j+1][k+_0],_5-_0); } if(dp5[(i-1)%2][j][k]!=-1) { ans=max(ans,k); dp5[i%2][j][k]=max(dp5[i%2][j][k],dp5[(i-1)%2][j][k]); int _2=v[i].fi,_5=dp5[(i-1)%2][j][k]+v[i].se; int _0=min(_2,_5); dp2[i%2][j+1][k+_0]=max(dp2[i%2][j+1][k+_0],_2-_0); dp5[i%2][j+1][k+_0]=max(dp5[i%2][j+1][k+_0],_5-_0); } } for(int j=0;j<=m;j++) for(int k=0;k<=18*N;k++) dp2[(i-1)%2][j][k]=dp5[(i-1)%2][j][k]=-1; } for(int j=0;j<=m;j++) for(int k=0;k<=18*N;k++) if(dp2[n%2][j][k]!=-1||dp5[n%2][j][k]!=-1) ans=max(ans,k); printf("%d",ans); return 0; }