joi2015ho B - ケーキの切り分け2(Cake 2)（難易度6）
久しぶりの更新
これでJOI難易度6は全部解き切った
解説
とりあえず円環をそのまま扱うのは難しいので、配列の長さを2倍にして複製する。
具体的には、A[0],A[1],…,A[N - 1]に、A[i] = A[i - N](N <= i <= 2 * N - 1)を付け加える。これで円環が扱いやすくなった。
次に、DPを考える。dp[i][j] = A[i]からA[j]のピースが残ってる時のJOIくんの取り分の最大値とする。
すると、求めるものはmax{dp[0][N - 1],dp[1][N],dp[2][N + 1],…,dp[N][2 * N - 1]}になる（最初の状態からJOIくんがどのケーキを取るかを全て網羅しているので）。
後はDPの遷移を考える。
残ってるピースの数から、JOIくんのターンかIOIちゃんのターンか見分けることが出来る（N - (残ってるピースの数)が偶数ならJOIくんのターン、奇数ならIOIちゃんのターン）。
JOIくんのターンの時、JOIくんはどちらのピースも取れるので、dp[i][j] = max(dp[i + 1][j] + A[i],dp[i][j - 1] + A[j])
IOIちゃんのターンの時、IOIちゃんは取れる2つのピースのうち大きい方を選ぶので、dp[i][j] = dp[i + 1][j](A[i] > A[j]),dp[i][j - 1](A[i] < A[j])
よってこれをメモ化再帰ですることによって解ける。