AOJ 2439 Hakone
問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2439
解法
先に'-'を取り除いておく。
1位から順に上から頂点を並べれば、適当な条件を満たすマッチングの数え上げの問題になる。
これはDPで解ける。
dp[i][j][k]:=i番目の頂点まで見ていて、左側にあるj個の頂点が未割り当てで、かつ右側にあるk個の頂点が未割り当てであるような割り当て方の総数
i番目の頂点がDのとき
(1) 右にあるi番目の頂点を、左側にある未割当の頂点と結ぶ
選び方はj通り。左側の未割当領域は1増えて1減るので変化なし。
dp[i+1][j][k]+=dp[i][j][k]*j
(2) 右にあるi番目の頂点を左側にある未割当の頂点と結び、左にあるi番目の頂点を右側にある未割当の頂点と結ぶ
選び方はjk通り。左側の未割当領域は1減り、右側の未割当領域も1減る。
dp[i+1][j-1][k-1]+=dp[i][j][k]*j*k
i番目の頂点がUのとき
(1) 割り当てない
選び方は1通り。左側の未割当領域は1増え、右側の未割当領域も1増える。
dp[i+1][j+1][k+1]+=dp[i][j][k]
(2) 左にあるi番目の頂点を右側にある未割当の頂点と結ぶ
選び方はk通り。左側の未割当領域は変化せず、右側の未割当領域も1増えて1減るので変化なし。
dp[i+1][j][k]+=dp[i][j][k]*k
よく考えると\(j=k\)が分かるので\(O(n^2)\)でも解ける。
ひとこと
今年の6月頃に解こうと思って諦めた問題。解けるようになって成長を感じる。