SRM515 Div1 Medium(550) NewItemShop

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);
}};