SRM403 Div2 1000

問題

4と7だけからなる数字はラッキーナンバーである．
ある整数nが与えられるとき，ラッキーナンバーの和でnとなる組み合わせを返す．複数の解があり得る場合は要素数が少ないもので，辞書順で早く来るものを返す．ここで辞書順とは2つの配列a1,a2があった場合，a1とa2が異なる数字となる最初の場所でa1の方が小さい数字となる場合をいう．解がない場合は空の配列を返す．

考え方

DP．
まず6桁分のすべてのラッキーナンバーを作って配列vに入れる．
dp[1000001]を用意し，dp[ i+v[j] ] = min(dp[ i+v[j] ], dp[i]+1)で更新する(dp[0]=0, otherwise INF)．dpはその数字を表すのに必要な要素の数を表す．
もし，dp[n]==INFなら解なし．
dp[n]==pならば，dp[ n-v[i] ]==p-1となる場所を探して解にv[i]を入れる．
次はn-v[i]の場所で同様に探してpが0になるまで繰り返す．

反省

ある数だけからなる数字を生成するにはdfsで(10*ret+ある数)とやれば作ることができる．
これはproject eular 303で反省したこと．
ある数字の組み合わせでnを作るような問題はdpとバックトレース．(ナップザック問題)