rt,二进制优化后反而WA?????
求大佬指正
code:
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
int n,m,maxn,ans=inf,cnt;
int sum[100100],cos[100100],coss[100100],val[100100];
int f1[100100],f2[100100];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",&coss[i]),maxn=max(maxn,coss[i]);
for(int i=1;i<=n;++i)
{
int b;
scanf("%d",&b);
int bas=1;
while(b>=bas)
{
b-=bas;
cos[++cnt]=coss[i]*bas;
val[cnt]=bas;
bas*=2;
}
if(b)
{
cos[++cnt]=coss[i]*b;
val[cnt]=b;
b=0;
}
}
memset(f1,0x3f,sizeof(f1));
memset(f2,0x3f,sizeof(f2));
f1[0]=f2[0]=0;
int top=m+maxn*maxn;
for(int i=1;i<=n;++i)
for(register int j=cos[i];j<=top;++j)f2[j]=min(f2[j],f2[j-cos[i]]+1);
n=cnt;
for(int i=1;i<=n;++i)
for(register int j=top;j>=cos[i];--j)f1[j]=min(f1[j],f1[j-cos[i]]+val[i]);
for(int i=m;i<=top;++i)ans=min(ans,f1[i]+f2[i-m]);
ans=min(ans,f1[m]);
if(ans==inf)printf("-1");
else printf("%d",ans);
return 0;
}