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;
}