SRM565 Div1 Easy(250) MonstersValley

TopCoder

MonstersValley

動的計画法。必要なコストごとに、最高のdreadを覚えておく。

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

class MonstersValley{public:
int minimumPrice( vector<long long> dread, vector <int> price )
{
    int n = (int)dread.size();

    vector<long long> T(2*n+1,-1);
    T[0] = 0;

    for ( int i=0; i<n; i++ )
    {
        vector<long long> P = T;
        T = vector<long long>(2*n+1,-1);
        for ( int j=0; j<=2*n; j++ )
        if ( P[j]>=0 )
        {
            T[j+price[i]] = max( T[j+price[i]], P[j]+dread[i] );
            if ( P[j]>=dread[i] )
                T[j] = max( T[j], P[j] );
        }
    }

    for ( int i=0; i<=2*n; i++ )
        if ( T[i]>=0 )
            return i;
    return -1;
}};