AOJ 0154 - Sum of Cards

dpじゃなくてメモ化ですね．

#include<iostream>
#include<algorithm>

int a[7], b[7], m, dp[7001][7];

//次i
int rec(int n, int i){
	if(n >= 0 && i < m && dp[n][i] != -1){
		return dp[n][i];
	}

	if(n == 0){
		return 1;
	}

	if(n < 0 || i >= m){
		return 0;
	}

	int res = 0;
	for(int j=0;j<=b[i];j++){
		res += rec(n-a[i]*j, i+1);
	}

	return dp[n][i] = res;
}

int main(){
	while(std::cin >> m, m){
		for(int i=0;i<7001;i++){
			for(int j=0;j<7;j++){
				dp[i][j] = -1;
			}
		}
		for(int i=0;i<m;i++){
			std::cin >> a[i] >> b[i];
		}
		int g, n;
		std::cin >> g;
		for(;g--;){
			std::cin >> n;
			std::cout << rec(n, 0) << std::endl;;
		}
	}
}