ケーキの切り分け２(15本選2)

N個に切られたホールケーキがあり、それぞれの大きさが与えられる。

先攻はまず好きなピースを取り、それ以降後攻は空間が隣にあるケーキの内で大きいほうのケーキを、先攻はそのようなケーキの内好きなほうを取る。

先攻の大きさを最大化しようという問題。

N<=2000なので、dp[iから][jまでのケーキが残っているときの]これ以降取れるケーキの大きさの和の最大値、でDPを組む。

計算量はO(N^2)

難易度は7程度に感じられた

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2315643#1