POJ-1742, TJU-3320 : Coins
問題概要
N(<100)種類のコインがある。価値がA[i](<10^5), 枚数がC[i](<10^3)枚ある。これらを用いて作ることのできる金額の種類は[1..M](M<10^5)に何枚あるか求める問題。
解法
蟻本p.62と同じ。
計算量O(N*M)。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAX_N = 100; const int MAX_M = 100000; int dp[2][MAX_M + 1]; int N, M; int as[MAX_N], cs[MAX_N]; bool init(){ scanf("%d%d", &N, &M); if(N==0 && M==0){ return false; } for(int i=0; i<N; i++){ scanf("%d", as+i); } for(int i=0; i<N; i++){ scanf("%d", cs+i); } return true; } int solve(){ int *cur, *nxt; memset(dp, -1, sizeof(dp)); cur = dp[0]; nxt = dp[1]; cur[0] = 0; for(int i=0; i<N; i++){ memset(nxt, -1, sizeof(dp[0])); for(int j=0; j<=M; j++){ if( cur[j] >= 0 ){ nxt[j] = cs[i]; } else if( as[i] <= j && nxt[j - as[i]] >= 1){ nxt[j] = nxt[j - as[i]] - 1; } } swap(cur, nxt); } int ans = 0; for(int i=1; i<=M; i++){ if(cur[i] >= 0){ ans++; } } return ans; } int main(){ while( init() ){ printf("%d\n", solve()); } return 0; }