POJ1742 Coins

問題 (http://poj.org/problem?id=1742)

n種類のコイン ,,・・・が、それぞれ, , ・・・枚ある。
m円以下の価格を、何種類お釣りなしに支払うことができるか。

最初は、動的計画法を用いず、setで一意性を担保し全てを足していったが案の定TLE。
個数制限付き部分和を用いたところ、通った。

#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <set>

using namespace std;

#define MAX_N 100
#define MAX_M 100000

int N, M;
int coin[2][MAX_N];
int dp[MAX_M+1];


void solve(){
  int cnt = 0;
  fill(dp, dp+MAX_M+1, -1);
  for(int i=0; i<N; i++){
    dp[0] = true;
    for(int j=0; j<=M; j++){
      if(dp[j] >= 0)dp[j] = coin[1][i];
      else if((j<coin[0][i]) || dp[j-coin[0][i]]<=0) dp[j] = -1;
      else dp[j] = dp[j-coin[0][i]]-1;
      if(i==N-1 && dp[j]>=0)cnt++;
    }
  }
  cout << cnt-1 << endl;
}

int main(){
  scanf("%d %d", &N, &M);
  while((N!=0) || (M!=0)){
    for(int i=0; i<N; i++){
      scanf("%d", &coin[0][i]);
    }
    for(int i=0; i<N; i++){
      scanf("%d", &coin[1][i]);
    }
    solve();
    scanf("%d %d", &N, &M);
  } 
  return 0;
}