假如说我这么写
#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[1000010],v[10010],w[10010];
int b[100010];
int sum;
int d[100010];
signed main()
{
int m,B,T=-1;
cin>>B>>m;
for(int i=1;i<=1000010;i++)dp[i]=1e9;
for(int i=1;i<=m;i++)
{
cin>>v[i];
w[i]=1;
}
int now=0;
for(int i=1;i<=B;i++)
{
cin>>d[i];
d[i]-=now;
now+=d[i];
if(now!=0)
{
now--;
}
if(d[i]<0)
{
cout<<"-1";
return 0;
}
}
dp[0]=0;
for(int i=1;i<=m;i++)
{
for(int j=v[i];j<=1e5;j++)
{
dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
}
}
int sum=0;
for(int i=1;i<=B;i++)
{
if(dp[d[i]]==1e9)
{
cout<<"-1";
return 0;
}
sum+=dp[d[i]];
}
cout<<sum;
return 0;
}
就能AC。
但是我如果初始化用
#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[1000010],v[10010],w[10010];
int b[100010];
int sum;
int d[100010];
signed main()
{
int m,B,T=-1;
cin>>B>>m;
memset(dp,0x7f7f7f,sizeof(dp));
for(int i=1;i<=m;i++)
{
cin>>v[i];
w[i]=1;
}
int now=0;
for(int i=1;i<=B;i++)
{
cin>>d[i];
d[i]-=now;
now+=d[i];
if(now!=0)
{
now--;
}
if(d[i]<0)
{
cout<<"-1";
return 0;
}
}
dp[0]=0;
for(int i=1;i<=m;i++)
{
for(int j=v[i];j<=1e5;j++)
{
dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
}
}
int sum=0;
for(int i=1;i<=B;i++)
{
if(dp[d[i]]==1e9)
{
cout<<"-1";
return 0;
}
sum+=dp[d[i]];
}
cout<<sum;
return 0;
}
第三个hack就过不去
求各位大佬指导