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

SRM 554 Div2 Medium TheBrickTowerMediumDivTwo

問題

塔の高さ配列が与えられ,この塔を一列に並べる.その際,倒れた塔があったとしても,隣接する塔に影響がないほどに離す.最初の塔から最後の塔までが最小になる時の等の並びを答えよ.

解答

全探索する.入力の等の個数が7つなので全探索して十分に間に合う.

class TheBrickTowerMediumDivTwo {
public:
  vector <int> find(vector <int> heights) {
    int n = heights.size();
    vector <int> idx(n);
    int resv = 0;
    for(int i = 0; i < n; i++) {
      idx[i] = i;
      if (i < n-1){
        resv += max(heights[i], heights[i+1]);
      }
    }

    vector<int> res = idx;
    while(next_permutation(idx.begin(), idx.end())){
      int total = 0;
      for (int i = 0; i < n-1; i++){
        total += max(heights[idx[i]], heights[idx[i+1]]);
      }
      if (resv > total){
        resv = total;
        res = idx;
      }
    }
    return res;
  }
}