AW281 硬币

题目地址


易错点:

  • 枚举剩余体积时需要正向遍历.(有效遍历状态)
  • 每组数据都需要重置计数数组(f[]),并设置f[0]=true(边界条件).

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int MAXN=2e2,MAXM=2e5;
int a[MAXN],c[MAXN];
int used[MAXM];//使用数量 
bool f[MAXM];//能否拼成 
int main(){
	while(1){
		int n,m;
		scanf("%d%d",&n,&m);
		if(!n||!m)return 0;
		memset(f,0,sizeof(f));
		f[0]=1;
		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
		for(int i=1;i<=n;i++)scanf("%d",&c[i]);
		for(int i=1;i<=n;i++){
			memset(used,0,sizeof(used));
			for(int j=a[i];j<=m;j++){//剩余体积 
				if(!f[j]&&f[j-a[i]]&&used[j-a[i]]+1<=c[i]){
					f[j]=1;
					used[j]=used[j-a[i]]+1;
				}
			}
		}
		int ans=0;
		for(int i=1;i<=m;i++){
			if(f[i])ans++;
		}
		printf("%d
",ans);
	}
	return 0;
}
原文地址:https://www.cnblogs.com/zbsy-wwx/p/11680556.html