萌新求助
查看原帖
萌新求助
110694
ChengZe楼主2020/10/14 23:07

WA了第57个点,爆了long long我这程序有哪里会爆吗。|——分割——|本人思路比较奇特,dp[i,j]表示选i个;j-maxa为正数表示余下来5的个数=j-maxa,j-maxa为负数表示余下来2的个数=maxa-j;dp内容表示该状态下的答案最大值

#include <bits/stdc++.h>
#define ll long long
const long long longmin=-0x7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7e;
using namespace std;
const int maxn=210,maxa=10000;
int minn,maxx,n,k;
ll x2[maxn],x5[maxn],x10[maxn],dp[maxn][maxa*2];
ll a;
ll ans;
int main()
{
	for(int i=0;i<maxn;i++)
	for(int j=0;j<maxa*2;j++)dp[i][j]=longmin/maxn;
	dp[0][maxa]=0;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a);
		while(a%2==0)x2[i]++,a/=2;
		while(a%5==0)x5[i]++,a/=5;
		x10[i]=min(x2[i],x5[i]);
		x2[i]-=x10[i];x5[i]-=x10[i];
		minn+=x2[i];maxx+=x5[i];
	}
	minn=maxa-minn;maxx=maxa+maxx;
	for(int now=1;now<=n;now++){
		if(x5[now]!=0&&x2[now]==0)for(int i=k;i>=1;i--){
			for(int j=maxx;j>=maxa+x5[now]+1;j--)dp[i][j]=max(dp[i][j],dp[i-1][j-x5[now]]+x10[now]);
			for(int j=maxa+x5[now];j>=maxa+1;j--)dp[i][j]=max(dp[i][j],dp[i-1][j-x5[now]]+x10[now]+x5[now]-(j-maxa));
			for(int j=maxa;j>=minn;j--)dp[i][j]=max(dp[i][j],dp[i-1][j-x5[now]]+x10[now]+x5[now]);
		}
		if(x5[now]==0&&x2[now]!=0)for(int i=k;i>=1;i--){
			for(int j=minn;j<=maxa-x2[now];j++)dp[i][j]=max(dp[i][j],dp[i-1][j+x2[now]]+x10[now]);
			for(int j=maxa-x2[now]+1;j<=maxa;j++)dp[i][j]=max(dp[i][j],dp[i-1][j+x2[now]]+x10[now]+x2[now]-(maxa-j));
			for(int j=maxa+1;j<=maxx;j++)dp[i][j]=max(dp[i][j],dp[i-1][j+x2[now]]+x10[now]+x2[now]);
		}
		else if(x5[now]==0&&x2[now]==0&&x10[now]!=0)for(int i=k;i>=1;i--)for(int j=maxx;j>=minn;j--)dp[i][j]=max(dp[i][j],dp[i-1][j]+x10[now]);
	}
	for(int i=1;i<=k;i++)
	for(int j=minn;j<=maxx;j++)ans=max(ans,dp[i][j]);
	printf("%lld\n",ans);
	return 0;
 } 
2020/10/14 23:07
加载中...