SRM501 Div1 Easy(250), Div2 Medium(500) FoxPlayingGame

FoxPlayingGame

動的計画法。負値を掛けてスコアを最大にするためには最小値が必要となるので、move Aをa回とmove Bをb回行った時のスコアの最大値と最小値を覚えておく。

#include <vector>
#include <cfloat>
using namespace std;

class FoxPlayingGame{public:
double theMax( int nA, int nB, int paramA, int paramB )
{
    double A = paramA / 1000.;
    double B = paramB / 1000.;

    vector<vector<double> > Smax( nA+1, vector<double>( nB+1, -DBL_MAX ) );
    vector<vector<double> > Smin( nA+1, vector<double>( nB+1,  DBL_MAX ) );
    
    Smax[0][0] = Smin[0][0] = 0;

    for ( int a=0; a<=nA; a++ )
    for ( int b=0; b<=nB; b++ )
    {
        if ( a>0 )
        {
            Smax[a][b] = max( Smax[a][b], Smax[a-1][b]+A );
            Smax[a][b] = max( Smax[a][b], Smin[a-1][b]+A );
            Smin[a][b] = min( Smin[a][b], Smax[a-1][b]+A );
            Smin[a][b] = min( Smin[a][b], Smin[a-1][b]+A );
        }

        if ( b>0 )
        {
            Smax[a][b] = max( Smax[a][b], Smax[a][b-1]*B );
            Smax[a][b] = max( Smax[a][b], Smin[a][b-1]*B );
            Smin[a][b] = min( Smin[a][b], Smax[a][b-1]*B );
            Smin[a][b] = min( Smin[a][b], Smin[a][b-1]*B );
        }
    }

    return Smax[nA][nB];
}};