AOJ : 0154 - Sum of Cards

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0154&lang=jp
日本語の問題文があるので省略です

アルゴリズム

動的計画法で解きました。
dp[i][j] には、カード[0]〜カード[i] までを使って、合計点を j にするための組み合わせ数が記憶されます。
ここでのアルゴリズムは、3重ループになっていますが、カードの種類数と枚数が非常に少ないので、計算時間は全くかかりません。
詳しくは、プログラムを見てください。

プログラム

#include <stdio.h>
#include <string.h>

int main(void){
  int i,j,k;
  int n,m,val,a[7],b[7];
  int dp[8][1001];

  while(scanf("%d",&n), n){
    for(i=0;i<n;i++){
      scanf("%d%d",&a[i],&b[i]);
    }

    memset(dp,0,sizeof(dp));
    dp[0][0] = 1;

    //カードの番号
    for(i=0;i<n;i++){
      //合計点
      for(j=0;j<=1000;j++){
        //i番目のカードを何枚使用するか
        for(k=0;k<=b[i];k++){
          if(j+a[i]*k>1000) continue; //1001以上はいらないので無視
          dp[i+1][j+a[i]*k] += dp[i][j];
        }
      }
    }

    scanf("%d",&m);
    while(m--){
      scanf("%d",&val);
      printf("%d\n",dp[n][val]);
    }
  }

  return 0;
}