This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
コインの価値が与えられる．同じコインを何枚でも使って良いので$1 \sim X$を全て表せる，コインの枚数を最小化したい．
$$
dp[i] := 現在持っているコインで価値iを表せるか
$$
として動的計画法．出来るだけ少ない枚数にしたいので，大きい数から減らせるだけ減らしていく．同じ配列を使ってしまうと何個も同じ数を使うdpになってしまうので，配列は分ける．最終的に$1 \sim X$全ての数字を表せているかをチェックする．
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
using namespace std ;
typedef long long ll ;
typedef pair < int , int > P ;
class Shopping {
public :
int minNumber ( int X , vector < int > values ) {
sort ( values . begin (), values . end ());
vector < bool > dp ( 1005 );
dp [ 0 ] = true ;
vector < int > ans ;
REP ( i , 1 , X + 1 ) {
if ( dp [ i ]) continue ;
int res = i ;
vector < int > v ;
for ( int j = values . size () - 1 ; j >= 0 ; j -- ) {
if ( res - values [ j ] >= 0 ) {
res -= values [ j ];
v . push_back ( values [ j ]);
ans . push_back ( values [ j ]);
j ++ ;
}
if ( dp [ res ]) break ;
}
vector < bool > dp2 = dp ;
REP ( j , 0 , X + 1 ) {
if ( dp [ j ]) {
rep ( k , v . size ()) {
if ( j + v [ k ] <= X ) {
dp2 [ j + v [ k ]] = true ;
}
}
}
}
dp = dp2 ;
}
rep ( i , X + 1 ) {
if ( ! dp [ i ]) return - 1 ;
}
return ans . size ();
}
};