http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2405
解法をyosupoさんのブログとか見て理解したのでメモしておきます。
とりあえずどっかで多角形を切り開いて区間の問題にします。
普通に考えるとO(N^2)のDPになって、更新式は
[l r]に区間が張られているとき
dp(l,r)=dp(l+1,r-1)+dp(l,a)*dp(a+1,r)
[l r]に区間が張られていない時
dp(l,r)=dp(l,a)*dp(a+1,r)
ただしaはlから張られている区間のうちr未満で最大のものです。
ここから計算量を落としたいのですが、dp(区間)みたいな形で更新できないか考えてみます。
まずdp(l+1,r-1)だけに注目すると、dp(l+1, r-1)=dp(l+1,b)*dp(b+1,r-1)=dp(l+1,b)*dp(b+1,c)*dp(c+1,d)...*dp(x,r-1)
のようになって[l+1,b],[b+1,c]...[x,r-1]はすべて区間なので予め求めておけばdp(l+1,r-1)も求まります。
dp(l,a),dp(a+1,r)も同じように出来て、dp(l+1,r-1),dp(l,a),dp(a+1,r)を求める際に使われる区間にかぶりはありません。
さらに、使われる区間は[l,r]にカバーされるので、dp(l,r)を求める際の1回しか使われません。
よって区間を長さ順にsortしておけばならし計算O(M)でdp(0,n)を求めることができます。
実装の際は区間を保存するのではなく、区間の左の座標を覚えておくと実装が楽になります。
dpはまず定式化することが重要で、次に遷移をみてオーダーを減らすのが基本です。
少しadhocですが、基本に忠実にやれば解ける問題ではありました。
