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