SRM363 div2 hard
メモ化再起で書いた。n=15に脊髄反射でbitDP的な感じ。
cache[何回目][すでにインストールされているもの(bit)]でメモ化。
#include <string> #include <sstream> #include <vector> using namespace std; class CrazyComponents { public: double cache[55][(1<<15)]; vector<int> require[15]; vector<double> income; vector<double> expense; int k; int n; double rec(int time,int state) { double &r=cache[time][state]; if(r!=-1.0) ; else if(time==k) r=0.0; else { r=0.0; for(int i=0;i<n;i++) { double d=0.0; bool b=true; for(int j=0;j<require[i].size();j++) if( !((1<<require[i][j]) & state) ) b=false; d=rec(time+1,state)/(double)n; if(b) d=max(d,(rec(time+1,(state | (1<<i)))+income[i]-expense[i])/(double)n ); r+=d; } } return r; } double expectedProfit(int _k,vector<string> components, vector <int> _income, vector <int> _expense) { k=_k; n=_income.size(); for(int i=0;i<n;i++) { income.push_back((double)_income[i]); expense.push_back((double)_expense[i]); } for(int i=0;i<n;i++) { stringstream ss(components[i]); int a; while(ss >> a) require[i].push_back(a); } for(int i=0;i<=k;i++) for(int j=0;j<(1<<n);j++) cache[i][j]=-1.0; return rec(0,0); } };