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;
}