0154-Sum of Cards

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0154
個数制限付きナップサック問題かなあと思ってメモ化探索で実装。
がメモ化しなくても時間内に間に合う。

実装(C++)

#include <cstdio>
#include <cstring>
struct carddata{
	int no;
	int count;
};
carddata card[7];
int DP[8][1001];
int m,n,g;
int slove(int u,int sum){
	int res=0;
	if(sum==0){
		res=1;
	} else if(sum<0||u>=m){
		return 0;
	} else {
		if(DP[u][sum]>=0)return DP[u][sum];
		for(int i=0;i<=card[u].count;i++){
			res+=slove(u+1,sum-i*card[u].no);
		}
	}
	return DP[u][sum]=res;
}
int main() {
	int a,b;
	while(1){
		m=0;scanf("%d",&m);
		if(m==0) break;
		for(int i=0;i<m;i++){
			scanf("%d%d",&a,&b);
			card[i].no=a;
			card[i].count=b;
		}
		memset(DP,-1,sizeof(DP));
		scanf("%d",&g);
		for(int i=0;i<g;i++){
			scanf("%d",&n);
			printf("%d\n",slove(0,n));
		}
	}
	return 0;
}