0154:Sum of Cards

動的計画法で解いた。

dp[ i ][ j ]:=i番目までのカードでj円を作れるパターンの数

#include<iostream>

using namespace std;

int main(void){
  int m,a[8],b[8],g,n,dp[8][1001];

  while(cin >> m,m){

    for(int i=0;i<8;i++){
      for(int j=0;j<1001;j++){
	dp[i][j]=0;
      }
    }

    for(int i=0;i<m;i++)
      cin >> a[i] >> b[i];
    
    for(int j=0;j<=b[0];j++){
      dp[0][a[0]*j]++;
    }
    
    
    for(int i=0;i<m-1;i++){
      for(int j=0;j<1001;j++){
	for(int k=0;k<=b[i+1];k++){
	  if(j+(a[i+1]*k)<1001)
	    dp[i+1][j+(a[i+1]*k)]+=dp[i][j];
	}
      }
    }
    
    cin >> g;
    while(g--){
      cin >> n;
      cout << dp[m-1][n] << endl;
    }
  }

  return 0;
}