AOJ 0246 - Bara-Bara Manju

問題文 : ばらばら饅頭

解法 : まず, 2個の饅頭で作る組み合わせが最適である(らしい) ので, 2個で作れる饅頭の個数を貪欲法で求める. (証明できなかった).

その後は, ナップサック問題を解く要領でメモ化再帰を行う.
このように, 配列に値を持たせて行うDPをmapDPというらしい.

ソース :

#include <map>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

map<vector<int>, int> m;
vector<vector<int> > mp;

int getMax(vector<int> p, int sum)
{
	int a;
	if (m.find(p) != m.end()){
		return (m[p]);
	}
	
	if (sum < 10){
		return (m[p] = 0);
	}
	
	a = 0;
	for (int i = 0; i < (int)mp.size(); i++){
		vector<int> c = p;
		bool flag;
		flag = true;
		
		for (int j = 1; j < (int)mp[i].size(); j++){
			c[j] -= mp[i][j];
			if (c[j] < 0){
				flag = false;
				break;
			}
		}
		
		if (flag == true){
			a = max(a, 1 + getMax(c, sum - 10));
		}
	}
	
	return (m[p] = a);
}


void make(vector<int> t, int n, int lim)
{
	if (lim == 0 || n == 10){
		if (!lim){
			mp.push_back(t);
			m[t] = 1;
		}
		return;
	}
	
	for (int i = 0; i * n <= lim; i++){
		vector<int> tn = t;
		tn.push_back(i);
		make(tn, n + 1, lim - i * n);
	}
	
	return;
}

int main(void)
{
	int n;
	int ans;
	vector<int> num(10);
	vector<int> t;
	
	t.push_back(0);
	make(t, 1, 10);
	
	while (scanf("%d", &n) && n){
		
		fill(num.begin(), num.end(), 0);
		
		for (int i = 0; i < n; i++){
			int t;
			scanf("%d", &t);
			num[t]++;
		}
		
		ans = 0;
		
		for (int i = 1; i <= 4; i++){
			int m = min(num[i], num[10 - i]);
			ans += m;
			num[i] -= m; num[10 - i] -= m;
		}
		ans += num[5] / 2; num[5] %= 2;
		
		int s = 0;
		for (int i = 1; i <= 9; i++){
			s += i * num[i];
		}
		
		printf("%d\n", ans + getMax(num, s));
	}
	
	return (0);
}