RT.调了 1h 了,test13 一直输出 0,不知道怎么回事。
哪位大佬能告诉我哪错了,两个关注。
不用管它的时间复杂度。
#include <bits/stdc++.h>
using namespace std;
namespace Main
{
typedef long long ll;
const int maxn=205;
int n,k;
ll a[maxn];
struct Number
{
int two,five;
}num[maxn];
bool f[maxn][maxn][52][52];
void main()
{
bool flag=0,flag2=0;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
while(a[i]%2==0)
{
// printf("whi2: %d ",a[i]);
a[i]/=2;
num[i].two++;
flag|=1;
}
while(a[i]%5==0)
{
// printf("whi5: %d ",a[i]);
a[i]/=5;
num[i].five++;
flag2|=1;
}
// printf("\n");
}
f[0][0][0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=i;j++)
{
for(int sto_pt_orz=0;sto_pt_orz<=50;sto_pt_orz++)
{
for(int sto_lhx_orz=0;sto_lhx_orz<=50;sto_lhx_orz++)
{
if(j>0&&sto_pt_orz-num[i].two>=0&&sto_lhx_orz-num[i].five>=0)
f[i][j][sto_pt_orz][sto_lhx_orz]|=f[i-1][j-1][sto_pt_orz-num[i].two][sto_lhx_orz-num[i].five];
f[i][j][sto_pt_orz][sto_lhx_orz]|=f[i-1][j][sto_pt_orz][sto_lhx_orz];
}
}
}
}
int ans=0;
for(int sto_zgc_orz=0;sto_zgc_orz<=50;sto_zgc_orz++)
{//
for(int sto_pt_orz=0;sto_pt_orz<=50;sto_pt_orz++)
{
if(f[n][k][sto_zgc_orz][sto_pt_orz])
{
ans=max(ans,min(sto_zgc_orz,sto_pt_orz));
}
}
}
printf("%d",ans);
}
}
int main()
{
Main::main();
return 0;
}