萌新求助
查看原帖
萌新求助
696382
lovely_glg楼主2023/7/11 14:18

假如说我这么写

#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就过不去

求各位大佬指导

2023/7/11 14:18
加载中...