SRM515 Div2 Hard(1000) NewItemShopTwo

TopCoder

NewItemShopTwo

動的計画法。時刻ごと、それぞれの客が来たかどうかごとに最大期待値を覚えておく。

#include <string>
#include <vector>
#include <sstream>
using namespace std;

class NewItemShopTwo{public:
double getMaximum( vector <string> customers )
{
    double C[24][2] = {{0}};
    double P[24][2] = {{0}};

    for ( int i=0; i<2; 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;
    }

    double T[25][4] = {{0}};

    for ( int i=23; i>=0; i-- )
    for ( int j=0; j<4; j++ )
    {
        T[i][j] = T[i+1][j];
        for ( int k=0; k<2; k++ )
            if ( (j>>k&1)==0 && P[i][k]>0 )
                T[i][j] = max(T[i+1][j|1<<k],C[i][k]) * P[i][k]
                        + T[i+1][j] * (1-P[i][k]);
    }

    return T[0][0];
}};