読者です 読者をやめる 読者になる 読者になる

SRM 565 Div2 Medium MonstersValley2

問題

順番にモンスターと出会う.モンスターと出会った時,賄賂を贈ると仲間にできる.但し,賄賂にはお金がかかる.もし,仲間の怖さの総和が,出会ったモンスターの怖さの以上であれば,賄賂を送らなくても襲われることはない.

モンスターに襲われずに賄賂のコストを最少にしたとき,そのコストを答える問題.

解答

公式の解説ではバックトラックの方法を説明しているが,モンスターの数が20匹と小さいので各モンスターに賄賂を贈るか否かの2値のパターンを考え220のパターンを全探索し,そのパターンで襲われるかどうかを計算.襲われないならば,その時のコストを計算し,一番最少のコストを返せば良い.

class MonstersValley2
{
public:
  int minimumPrice(vector <int> dread, vector <int> price)
    {
      int n = dread.size();
      int i, j;
      long long minv = LONG_MAX;
      for (i = 0; i < 1 << n; i++){
        long long total_scairness = 0;
        long long total_price = 0;
        bool valid = true;
        for (j = 0; j < n; j++){
          bool bribe = (1 & (i >> j));
          if (bribe) {
            total_scairness += dread[j];
            total_price += price[j];
          }else if (total_scairness < dread[j]){
            valid = false;
            break;
          }
        }
        if (valid){
          minv = min(minv, total_price);
        }
      }
      return minv;
    }
};