＜問題＞
①モンスターの集合が与えられ、各モンスターは怖さの値とコインの値を持つ。
②プレイヤーは最初から順番にモンスターに遭遇する。
③このとき、プレイヤーはモンスターにそのコインの値を支払って仲間にすることができる。
④もしくは、仲間にしたモンスターの怖さの和がそのモンスターの怖さの値以上であれば、何もせずに通り過ぎることができる。それ未満であれば、仲間にしないといけない。
⑤このとき、すべてのモンスターに遭遇した後に最小のコイン消費枚数を返す。
＜解き方＞
まさに動的計画法。
参照用のvectorをグローバルで宣言してpush_backでコピーしようとしたんですが、
エラーが出たので引数で渡すことに。
suztomoさんのページを拝見させていただいたのですが、
１０＾７以上のループに加え、あまり大きな数を扱ってもダメなのかもしれないです。
http://topcoder.g.hatena.ne.jp/suztomo/20081208/1228768981
＜コード＞
class MonstersValley2 {
public:
int f(int cur, double cdread, vector<int> d, vector<int> p){
int coin=0;
if(cur==n)return 0;
if(cdread<d[cur])coin=p[cur]+f(cur+1,cdread+d[cur],d,p);
else coin=min(f(cur+1,cdread,d,p),f(cur+1,cdread+d[cur],d,p)+p[cur]);
return coin;
}
int minimumPrice(vector<int> dread, vector<int> price) {
n=dread.size();
return f(1,dread[0],dread,price)+price[0];
}
};
①モンスターの集合が与えられ、各モンスターは怖さの値とコインの値を持つ。
②プレイヤーは最初から順番にモンスターに遭遇する。
③このとき、プレイヤーはモンスターにそのコインの値を支払って仲間にすることができる。
④もしくは、仲間にしたモンスターの怖さの和がそのモンスターの怖さの値以上であれば、何もせずに通り過ぎることができる。それ未満であれば、仲間にしないといけない。
⑤このとき、すべてのモンスターに遭遇した後に最小のコイン消費枚数を返す。
＜解き方＞
まさに動的計画法。
参照用のvectorをグローバルで宣言してpush_backでコピーしようとしたんですが、
エラーが出たので引数で渡すことに。
suztomoさんのページを拝見させていただいたのですが、
１０＾７以上のループに加え、あまり大きな数を扱ってもダメなのかもしれないです。
http://topcoder.g.hatena.ne.jp/suztomo/20081208/1228768981
＜コード＞
class MonstersValley2 {
public:
int f(int cur, double cdread, vector<int> d, vector<int> p){
int coin=0;
if(cur==n)return 0;
if(cdread<d[cur])coin=p[cur]+f(cur+1,cdread+d[cur],d,p);
else coin=min(f(cur+1,cdread,d,p),f(cur+1,cdread+d[cur],d,p)+p[cur]);
return coin;
}
int minimumPrice(vector<int> dread, vector<int> price) {
n=dread.size();
return f(1,dread[0],dread,price)+price[0];
}
};
Share this
Related Posts
SRM 556 DIV2 -Level2
問題
①複数の地点が与えられて、それぞれの地点に値を持つ。
②また地点によっては道路で結ばれていて、
道路として結ばれている２次元配列が与えられる。
③ユーザは地点０から始まり、地点０のスコアを持つ。
④地点０から結ばれて- SRM 501 DIV1 Easy - FoxPlayingGame
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11284&rd=14430
・nA,nB,paramA,paramBが与えられる。
・最
- SRM 612 DIV1 Easy - EmoticonsDiv1 (××○)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=10543&rd=15845
・笑顔の顔文字をsmiles分送りたい。
・最初はsmile
- SRM 555 DIV1 Easy - CuttingBitString
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12155&rd=15177
解き方
ｄｐで解く。ｎは５０なので整数の最大は2^5