SRM515 Div1 Medium(550) NewItemShop
動的計画法。時刻、残りの剣数、それぞれの客が来たかどうかごとに最大期待値を覚えておく。客数は最大で24人だけど、1度しか来ない客が来たかどうかの情報は必要ない。1度に1人しか客が来ないという制約から、2回以上来る客は高々12人。
#include <string> #include <vector> #include <sstream> using namespace std; int n; double C[24][24]; double P[24][24]; int N[24]; double memo[24][25][1<<12]; double BT( int time, int sword, int visited ) { if ( time>=24 ) return 0; // N≧2となる客の分のビットのみを抽出 int v = 0; for ( int i=0; i<n; i++ ) if ( N[i]>=2 ) v = v<<1 | visited>>i&1; double &m = memo[time][sword][v]; if ( m >= 0 ) return m; for ( int i=0; i<n; i++ ) if ( (visited>>i&1)==0 && P[time][i]>0 ) { // 客が来た場合 double c1; if ( sword > 0 ) c1 = max( BT(time+1,sword-1,visited|1<<i) + C[time][i], BT(time+1,sword ,visited|1<<i) ); else c1 = BT(time+1,sword,visited|1<<i); // 客が来なかった場合 double c2 = BT(time+1,sword,visited); return m = c1*P[time][i] + c2*(1-P[time][i]); } return m = BT(time+1,sword,visited); } class NewItemShop{public: double getMaximum( int swords, vector <string> customers ) { n = (int)customers.size(); memset( C, 0, sizeof C ); memset( P, 0, sizeof P ); memset( N, 0, sizeof N ); for ( int i=0; i<n; i++ ) { for ( int j=0; j<(int)customers[i].size(); j++ ) if ( customers[i][j]==',' ) customers[i][j] = ' '; stringstream ss(customers[i]); int t,c,p; int s = 100; while ( ss>>t>>c>>p ) { C[t][i] = c; P[t][i] = (double)p/s; s -= p; N[i]++; } } for ( int i=0; i<24; i++ ) for ( int j=0; j<=swords; j++ ) for ( int k=0; k<1<<12; k++ ) memo[i][j][k] = -1; return BT(0,swords,0); }};