POJ1742

今回もDPの練習です。最初は入れ子ループを何重にも張り巡らしてしまい、タイムアウトしてしまいました。

あとコインが何枚残っているかをメモすれば効率化を計れるんですね。蟻本で読んだ覚えがあってもいざ自分で実装するとなると難しいです。

解答時間は1時間20分です。以下コードです

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

int n, m;
int a[100], c[100];
int dp[100001];
int sum = 0;

int solve(){
  sum = 0;
  memset(dp, -1, sizeof(dp));
  for(int i = 1; i <= m/a[0] && c[0] > 0; i++){
    dp[i*a[0]] = 0;
    c[0]--;
  }
  for(int i = 1; i < n; i++){
    dp[0] = c[i];
    for(int j = 1; j <= m; j++){
      if(dp[j] != -1){
        dp[j] = c[i];
      }else if(a[i] <= j && dp[j - a[i]] > 0){
        dp[j] = dp[j - a[i]] - 1;
      }
    }
  }
  for(int i = 1; i <= m; i++){
    if(dp[i] != -1){
      sum++;
    }
  }
  return sum;
}


int main(){
  while(1){
    scanf("%d %d", &n, &m);
    if(n == 0 && m == 0)
      break;
    for(int i = 0; i < n; i++){
      scanf("%d", &a[i]);
    }
    for(int i = 0; i < n; i++){
      scanf("%d", &c[i]);
    }
    printf("%d\n", solve());
  }
  return 0;
}