两个同样的代码把dp数组int->bool

然后50pts->100pts

AC代码

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=5e5+10;
int a[210],k[210],n,m,sum,t,dp[maxn];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&a[i],&k[i]),sum+=a[i]*k[i];
	//memset(dp,-1,sizeof(dp));
	dp[0]=1;
	for(int i=1;i<=n;i++){
		int tmp=k[i],tot=0;
	//	printf("k[%d]=%d\n",i,k[i]);
		for(int c=1;c<=k[i];c<<=1){
	//		printf("c=%d\n",c);
			for(int j=maxn;j>=a[i]*c;j--)
				if(dp[j-a[i]*c]) dp[j]=1;
			k[i]-=c;
		}
		if(k[i]){
	//	printf("c=%d\n",k[i]);
			for(int j=maxn;j>=a[i]*k[i];j--)
				if(dp[j-a[i]*k[i]]) dp[j]=1; 
		}
	}
	/*for(int i=0;i<=sum;i++)
		printf("dp[%d]=%d\n",i,dp[i]);*/
	for(int i=1;i<=m;i++){
		scanf("%d",&t);
		if(dp[t]==1) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}
/*
3 4
1 9
2 1
3 1
1 2 3 8
*/

记录

50pts代码

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=5e5+10;
int a[210],k[210],dp[maxn],n,m,sum,t;
int main(){
	//freopen("1in.txt","r",stdin);
	//freopen("my.txt","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&a[i],&k[i]),sum+=a[i]*k[i];
//	memset(dp,-1,sizeof(dp));
	dp[0]=1;
	for(int i=1;i<=n;i++){
		int tmp=k[i],tot=0;
	//	printf("k[%d]=%d\n",i,k[i]);
		for(int c=1;tot<=tmp;c<<=1){
	//		printf("c=%d\n",c);
			tot+=c;
			if(tot>tmp) break;
			for(int j=maxn;j>=a[i]*c;j--)
				if(dp[j-a[i]*c]) dp[j]=1;
			k[i]-=c;
		}
		if(k[i]){
	//	printf("c=%d\n",k[i]);
			for(int j=maxn;j>=a[i]*k[i];j--)
				if(dp[j-a[i]*k[i]]) dp[j]=1; 
		}
	}
	/*for(int i=0;i<=sum;i++)
		printf("dp[%d]=%d\n",i,dp[i]);*/
	for(int i=1;i<=m;i++){
		scanf("%d",&t);
		if(dp[t]) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}
/*
3 4
1 9
2 1
3 1
1 2 3 8
*/

记录