SRM 585 Div2 Medium TrafficCongestionDivTwo

問題

完全二分木で表される都市ネットワークが与えられる.複数の車を使って全ての都市を訪れる方法を考える.各車は2点の都市間を最短経路で訪れ,同じ都市には重複して訪れない.
開始都市と到着都市は同じでも構わない,その場合その車は一つの都市だけを訪れる.

解答

返り値がlong longなのでDPを使うんだろうなとぼんやりと考える.
最左の葉から最右の葉までを一回で辿り,残りの部分木の最適解を足し合わせると良いかなと予想をたてる.
これは各部分木の最適解を持っておけば求めることが出来る.
テストケースの高さ60の時で大丈夫なようで合っているようだ.
テストケースがしっかりしているので良心的な問題.多くの人が正解していた.

class TrafficCongestionDivTwo
{
public:
  long long theMinCars(int treeHeight)
    {
      long long M[65] = {};
      M[0] = 1;
      M[1] = 1;
      // M[2] = 1;
      int i, j;
      for(i = 2; i < 61; i++){
        M[i] = 1;
        for(j = 0; j < i-1; j++){
          M[i] += 2*M[j];
        }
      }
      return M[treeHeight];
    }
};