AOJ0246 Bara-Bara Manju

・基本的な解法はメモ化探索である。
・(1,9),(2,8),(3,5),(4,6),(5,5)はgreedyにまとめていい。
・残りの饅頭の状態は、N<=100なのでbitで持てる(ある意味bitDP?)。

これらのことをして、ハッシュマップでメモ化するとようやくACがもらえます。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <math.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <map>
 
using namespace std;
 
#define FOR(I,N) for(int I = 0; I < (int)(N); I++)
#define pb push_back
#define INF (1 << 30)
 
typedef pair<int, int> P;
 
string sValueOf(int v){stringstream ss;ss<<v;return ss.str();}
int parseInt(string v){int i;stringstream ss(v);ss>>i;return i;}

int manju[11];
 
map<int,int> memo;
map<int,int> comp;
 
int converter(int m[11]){///7bitで分割するとよさそう
    int ret = 0;
    FOR(i,5){
        if(comp.find(i)==comp.end())break;
        int tar = comp[i];
        ret+=m[tar]<<(7*i);
    }
    return ret;
}
 
vector<P> converter2(int bit){
    vector<P> ret;
    FOR(i,5){
        if(comp.find(i)==comp.end())break;
        int tar = comp[i];
        int v = (bit>>(i*7))&((1<<7)-1);
        if(v==0)continue;
        ret.pb(P(tar,v));
    }
    return ret;
}
 
struct Pt{
    int pt[11];
    Pt(){
        FOR(i,11)pt[i] = 0;
    }
};
 
vector<Pt> allpt;
 
int saiki(int bit){
    if(memo.find(bit)!=memo.end()){///メモされてるか確認
        return memo[bit];
    }
    int sum = 0;
    vector<P> ms = converter2(bit);
    int manj[11];fill_n(manj,11,0);
    FOR(i,ms.size())manj[ms[i].first] = ms[i].second;
    FOR(i,allpt.size()){
        Pt pt = allpt[i];
        bool can = true;
        FOR(j,11){
            if(pt.pt[j]>manj[j]){///饅頭足りない
                can = false;
            }
        }
        if(!can)continue;
        FOR(j,11)manj[j]-=pt.pt[j];
        sum = max(sum,saiki(converter(manj))+1);
        FOR(j,11)manj[j]+=pt.pt[j];
    }
    return memo[bit] = sum;
}
 
 
int tmp[11];
 
void makeAllpt(int sum){
    if(sum==10){
        Pt p = Pt();
        memcpy(p.pt,tmp,sizeof(tmp));
        allpt.pb(p);
        return;
    }
    for(int i = 1;i<=8;i++){
        if(!manju[i])continue;
        if(sum+i>10)continue;
        manju[i]--;
        tmp[i]++;
        makeAllpt(sum+i);
        tmp[i]--;
        manju[i]++;
    }
    return;
}
 
 
int main(){
    int i,j;
    int n,a,sum;
     
    while(cin>>n,n){
        memo.clear();
        comp.clear();
        allpt.clear();
        sum = 0;
        FOR(i,11)manju[i] = 0;
        FOR(i,n){
            cin>>a;
            manju[a]++;
        }
        for(int s = 9;s!=4;s--){
            while(manju[s]){
                if(!manju[10-s])break;
                if(s==5&&manju[s]==1)break;
                manju[s]--;
                manju[10-s]--;
                sum++;
            }
        }
        int count = 0;
        FOR(i,8){
            if(manju[i+1]&&(i+1)!=5){
                comp[count] = i+1;
                count++;
            }
        }
        comp[count] = 5;
        fill_n(tmp,11,0);
        makeAllpt(0);
        cout<<sum+saiki(converter(manju))<<endl;
    }
    return 0;
}

楽しくない(直球)