SRM 565 DIV1 Easy - MonstersValley

SRM 565 DIV1 Easy - MonstersValley

7:50

問題


http://community.topcoder.com/stat?c=problem_statement&pm=12350&rd=15187

モンスターが複数いる谷を越える。
各モンスターには恐さとコインの値を持つ。
プレイヤーは各モンスターに対し、そのコインを払って仲間にするか、
もしくは仲間の恐さの和がそのモンスター以上であればそのまま通り過ぎることが
できる。
このとき、全てのモンスターを越えたときに支払う最小のコインの数を求める。

解き方


モンスターの数が５０のため、Ｏ（２＾５０）となり
深さ優先探索では求めることができない。

ここでコインの数は最大でモンスターの数×２となるため、
モンスターの位置にいるとき所有しているコインの数をパラメータ、
返り値を恐さの値としたｄｐで解くことができる。

コード


class MonstersValley {

public:

int minimumPrice(vector<long long> dread, vector<int> price) {
int n=dread.size();
long long maxp[2*n+1][n+1],INF=1e+18;

FORE(p,0,2*n+1){
maxp[p][0]=0;
FORE(j,1,n+1)maxp[p][j]=-INF;
FORE(j,1,n+1){
if(p>=price[j-1])maxp[p][j]=maxp[p-price[j-1]][j-1]+dread[j-1];
if(maxp[p][j-1]>=dread[j-1])maxp[p][j]=max(maxp[p][j],maxp[p][j-1]);
}
}

FORE(i,0,2*n)if(maxp[i][n]>=0)return i;
return 2*n;;
}

};


using namespace std;

#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

long long dp[51][200];

class MonstersValley {

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

FORE(i,0,51)FORE(j,0,200)dp[i][j]=-1e+18;
dp[0][0]=0;
FORE(i,0,n)FORE(j,0,150){
if(dp[i][j]>=0){
dp[i+1][j+price[i]]=max(dp[i+1][j+price[i]],dp[i][j]+dread[i]);
if(dp[i][j]>=dread[i])dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
}
}

FORE(i,0,200)if(dp[n][i]>=0)return i;
return 2*n;

}

};

Share this

Google Facebook Twitter More

Related Posts