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.
$i$を表現するのにマッチが$matches[i]$本必要となる．$n$本ある時，作れる最大値はいくつか．
問題文にあるが$0$を表現するのに$8$本必要というのはどういう状況なのか，ちょっと面白い問題設定．
$$
dp[i][j] := i桁の数でマッチの本数が残りjの時の最大値
$$
として動的計画法．$matches[i]$本使って，$dp[i][j]$の末尾に付け加える．$n \leq 50$なので$dp[i][j]$から全て試し，次の状態の$max$を取った．単純な文字列比較では辞書順になるので，ちゃんと桁を見て判断するようにした．またzero-leadingになっていはいけないので先頭が$0$のものからは遷移させないようにした．
Code
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
69
70
71
#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 ;
string dp [ 55 ][ 55 ];
string f ( string s , string t ) {
if ( s . size () == t . size ()) {
bool flag = true ;
rep ( i , s . size ()) {
if ( s [ i ] > t [ i ]) break ;
if ( s [ i ] == t [ i ]) continue ;
flag = false ;
}
if ( flag ) return s ;
return t ;
} else {
if ( s . size () > t . size ()) return s ;
else return t ;
}
}
class MatchNumbersEasy {
public :
string maxNumber ( vector < int > matches , int n ) {
int m = matches . size ();
rep ( i , 55 ) rep ( j , 55 ) dp [ i ][ j ] = "" ;
rep ( i , 54 ) {
string res = "" ;
for ( int j = n ; j >= 0 ; j -- ) {
rep ( k , m ) {
int x = j - matches [ k ];
char c = char ( '0' + k );
if ( x >= 0 && dp [ i ][ j ][ 0 ] != '0' ) {
dp [ i + 1 ][ x ] = f ( dp [ i + 1 ][ x ], dp [ i ][ j ] + c );
}
}
}
}
string ans = "" ;
rep ( i , 55 ) {
rep ( j , n + 1 ) {
ans = f ( ans , dp [ i ][ j ]);
}
}
return ans ;
}
};