SRM 565 DIV1 Easy - MonstersValley (復習××)
問題
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;;
}
};
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;
}
};
#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;
}
};
