N個に切られたホールケーキがあり、それぞれの大きさが与えられる。
先攻はまず好きなピースを取り、それ以降後攻は空間が隣にあるケーキの内で大きいほうのケーキを、先攻はそのようなケーキの内好きなほうを取る。
先攻の大きさを最大化しようという問題。
N<=2000なので、dp[iから][jまでのケーキが残っているときの]これ以降取れるケーキの大きさの和の最大値、でDPを組む。
計算量はO(N^2)
難易度は7程度に感じられた
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2315643#1
