AOJ 0246 Bara-Bara Manju
問題
n個のまんじゅうがあり、それぞれの重さは1〜9の整数である。
重さがちょうど10になるようにまんじゅうを選びたい。
重さがちょうど10のまんじゅうのグループは最大でいくつできるか、求めよ。
制約条件
n≦100
方針
1と9, 2と8, 3と7, 4と6, 5と5のまんじゅうは、グループにしてしまっても損はしない。
なので、まずこれらの組を貪欲に作る。
残ったまんじゅうは探索で10のできる数を求める。
下のコードでは適当にmapとvectorでメモ化した。
途中経過も全部メモ化すると多分MLEなので、現在作っているグループが空のときだけメモ化するようにした。
ソースコード
int n, a[10], b[10], m; map<vi, int> dp; int rec(vi &v, int cur, int sum){ bool cnt = 0; if(sum == 10){ cnt = 1; cur = 0; sum = 0; } if(sum == 0){ if(dp.count(v)) return dp[v]; } if(cur >= m || sum + b[cur] > 10) return 0; int res = 0; if(v[cur]){ v[cur]--; res = max(res, rec(v, cur, sum + b[cur])); v[cur]++; } res = max(res, rec(v, cur + 1, sum)); res += cnt; if(sum == 0) dp[v] = res; return res; } int main() { while(cin >> n, n){ rep(i, 10) a[i] = 0; rep(i, n){ int x; cin >> x; a[x]++; } int ans = 0; for(int i = 1; i < 5; i++){ int x = min(a[i], a[10 - i]); ans += x; a[i] -= x; a[10 - i] -= x; } ans += a[5] / 2; a[5] %= 2; m = 0; vi v; rep(i, 10) if(a[i]){ b[m++] = i; v.pb(a[i]); } dp.clear(); ans += rec(v, 0, 0); cout << ans << endl; } return 0; }