初詣 [yukicoder No.842] - はまやんはまやんはまやん

解説

解くためのアルゴリズムとしては、各小銭について何枚とるかというのを全探索すると、
O(ABCDEF)で、これは10^6なので間に合う。
問題が実装なのだが、rep記法とかを使っていれば6乗ループもそんなに怖くないので、書いてもいい。
今回はdfsを使って、こういう場合の全探索方法を紹介しておく。
　
use[i] := i種類目の小銭を何枚使うか
というのを構築しながら、dfsしていく。
dfs(cu) := cu種類目までのuseが確定しているときの、それ以降の組み合わせについてYESになる場合があればtrue
これを使って、順番にuseを埋めていく。
　
cu=6の場合は、useが全部埋まっているということなので、use配列を使って、総和を求めて=Gか判定する。
=Gであれば、trueを返す。
　
そうでない場合は、cu番目を今から埋めるということなので、埋める。
可能性としては、0枚～持っている最大枚数の使えるパターンがあるので、そのパターン分ループする。
use[cu]をそれで埋めて、dfs(cu+1)を呼ぶ。
これで、cu番目を確定させて、それ以降をまた再帰で処理させることができる。
このやり方で全探索ができるのだが、慣れていないと難しいかもしれない。
練習が必要。

int have[6];
int yen[6] = { 500, 100, 50, 10, 5, 1 };
int G;
//---------------------------------------------------------------------------------------------------
int use[6];
bool dfs(int cu) {
	if (cu == 6) {
		int sm = 0;
		rep(i, 0, 6) sm += use[i] * yen[i];
		if (sm == G) return true;
		else return false;
	}

	rep(i, 0, have[cu] + 1) {
		use[cu] = i;
		if (dfs(cu + 1)) return true;
	}

	return false;
}
//---------------------------------------------------------------------------------------------------
void _main() {
	rep(i, 0, 6) cin >> have[i];
	cin >> G;

	if (dfs(0)) cout << "YES" << endl;
	else cout << "NO" << endl;
}