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; }
楽しくない(直球)