yaoshimax https://blog.hatena.ne.jp/yaoshimax/ 不定期プログラミング覚え書き https://yaoshimax.hatenablog.com/ 問題 No.364 門松木 - yukicoder すべての隣り合う３ノードが門松列になっている木を門松木と呼ぶ。 入力に木が与えられるので、その部分木である門松木のがもつ門松列の個数の最大値を答えよ 考えたこと どう見ても木DPです……と思ってからDPを実装可能な状況にするまでに凄い時間かかった。 最終的に、 dp[n][o][f]: ノードnが両端のノードより大きい(o=0)/小さい(o=1)ような、門松木の最大の門松列の数。 但し、f=0の時はparent[n]を考慮せず、nとその子孫のみで門松木を作った場合で、f=1の時にはparent[n]を必ず利用する場合の値（なおかつ、paren… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fyaoshimax.hatenablog.com%2Fentry%2F2016%2F04%2F25%2F004818" title="yukicoder #364: 門松木 - 不定期プログラミング覚え書き" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2016-04-25 00:48:18 rich https://yaoshimax.hatenablog.com/entry/2016/04/25/004818 1.0 100%