競プロはじめました

競プロ初心者のブログ

POJ1742

POJ1742

1742 -- Coins

今回も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;
}