AOJ 0246 Bara-Bara Manju

問題

問題リンク：ばらばら饅頭

解法

各重さの饅頭の個数を状態に持ってメモ化再帰をすることを思いつくが より、最悪 程度のパターンが存在するため厳しい。

パターンを減らすため、先に決めて損のない組み合わせを貪欲に取り除いておくことを考える。すると、1-9, 2-8, 3-7, 4-6, 5-5 は貪欲に組み合わせてもよいことがわかる。

例えば、1+x=10という組があったとき、xが9未満の数で構成されているならばxを9に置き換えても組の個数は減らない。xで構成されていた数は9よりも自由度が高い(他の組み合わせで使える可能性がある)から、必ず損にはならない。よって、1と9は貪欲に組にしてよい。同様の議論がその他のペアについても言える。

以上の貪欲で個数を減らすと、個数が0であるような重さが最低4つはできるので、パターン数が 程度に抑えられ十分間に合うようになる。

コメント

配列をkeyに持つmapを使うと比較的楽に実装できると思う。 あと、DP配列の初期化を忘れない(自戒)。

Code

#include <bits/stdc++.h>
using namespace std;

map<vector<int>, int> dp;

int rec(vector<int> &v, int sum){
    if(dp.count(v)) return dp[v];
    int res = 0;
    for(int i=1; i<=9; i++){
        if(v[i]>0 && sum+i<=10){
            v[i]--;
            res = max(res, rec(v, (sum+i)%10)+(sum+i)/10);
            v[i]++;
        }
    }
    return dp[v] = res;
}

int main() {
    int n;
    while(cin >> n, n){
        vector<int> v(10,0);
        dp.clear();
        int ans = 0;
        for(int i=0;i<n;i++){
            int a;
            cin >> a;
            v[a]++;
        }
        // 貪欲で数を減らす
        for(int i=1;i<=4;i++){
            int tmp = min(v[i], v[10-i]);
            ans += tmp;
            v[i] -= tmp;
            v[10-i] -= tmp;
        }
        ans += v[5]/2;
        v[5] %= 2;

        ans += rec(v, 0);
        cout << ans << endl;
    }
    return 0;
}