SRM565 Div1 Medium(500) MonstersValley2

TopCoder

MonstersValley2

全探索。

#include <vector>
using namespace std;

class MonstersValley2{public:
int minimumPrice( vector <int> dread, vector <int> price )
{
    int n = (int)dread.size();
    int ans = 2*n;
    for ( int i=0; i<1<<n; i++ )
    {
        int p = 0;
        long long d = 0;
        bool f = true;
        for ( int j=0; j<n && f; j++ )
        {
            if ( i>>j&1 )
            {
                d += dread[j];
                p += price[j];
            }
            else
            {
                if ( d<dread[j] )
                    f = false;
            }
        }

        if ( f )
            ans = min( ans, p );
    }

    return ans;
}};