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

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #382 (Div. 1) C: Ostap and Tree

http://codeforces.com/contest/736/problem/C

問題概要

木が与えられる。頂点を黒か白で塗りつぶす。どの白頂点も距離K以内に黒頂点があるような塗りつぶし方は何通りあるか。

  • 1≦n≦100
  • 0≦k≦min(20,n-1)

解法

dp[頂点][根から最も近い黒頂点の深さ][根から最も遠い黒に支配されていない白頂点の深さ]:=パターン数としてDPをする。

j+k'+1≦Kであれば右側の未支配頂点が消滅し、j'+k+1≦Kであれば左側の未支配頂点が消える。消えないならそのまま残る。

f:id:pekempey:20161129224554p:plain

なかなか面倒なDP。結構バグらせてしまったので、Dに逃げたのはよかったかも。