JOI2014 本戦 ケーキの切り分け2(Cake 2)

問題

Cake 2 | Aizu Online Judge

問題概要

円形にN個に切られたケーキ(サイズA[i]は全て異なる)について以下のような行動を考える。
1:JOI君とIOIちゃんの二人で交互に進める
2:JOI君が先行で、最初は好きなケーキを選べる
3:IOIちゃんは取ることのできるケーキのうちもっとも大きなケーキを取る
4:JOI君は取ることのできるケーキのうち好きなものを選ぶことができる
5:取ることのできるケーキとは、両隣の少なくともどちらか一方が今までの行動で取られたケーキでなければならない。
JOI君が食べるケーキの合計値の最大値を求めよ

解法

ミニマックス法で解く。
その際、dp[l][r][turn] := [l,r]のケーキを取った時のJOI君の得点の最大値(turnは今見ている状態がIOI君かJOI君のどちらのターンか)を保存するようにしてメモ化再帰で実装する。

コード

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <queue>
#include <complex>
 
#define INF 100000000
#define INF_INT_MAX 2147483647
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
 
using namespace std;

#define MAX_N 2001

int N;
LL A[MAX_N];
//[l,r]を使った時のJOI君が取れる得点の最大値
LL dp[MAX_N][MAX_N][2];

bool Input(){
  cin >> N;
  for(int i = 0; i < N; i++){
    cin >> A[i];
  }
  return true;
}

void InitDP(){
  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      dp[i][j][0] = dp[i][j][1] = -1;
    }
  }
}

//posが配列の範囲外に出てたら座標値を変換する
int ConvPos(int pos){
  if(pos < 0)
    pos = N-1;
  else if(pos >= N)
    pos = 0;
  return pos;
}

//turn = 0: JOI君のターン turn = 1: IOIちゃんのターン
LL Solve(int l, int r, int turn = 1, int cnt = 1){

  if(cnt == N)
    return 0;

  if(dp[l][r][turn] >= 0)
    return dp[l][r][turn];

  if(turn == 1){
    LL ret;
    if(A[ConvPos(l-1)] > A[ConvPos(r+1)])
      ret = Solve(ConvPos(l-1), r, 0, cnt+1);
    else
      ret = Solve(l, ConvPos(r+1), 0, cnt+1);
    return dp[l][r][turn] = ret;
  }

  else{    
    LL ret = max(Solve(ConvPos(l-1), r, 1, cnt+1) + A[ConvPos(l-1)],
		 Solve(l, ConvPos(r+1), 1, cnt+1) + A[ConvPos(r+1)]);
    return dp[l][r][turn] = ret;
  }

}

int main(){

  Input();

  LL ans = 0;

  InitDP();

  for(int i = 0; i < N; i++){
    ans = max(ans,Solve(i,i) + A[i]);
  }

  cout << ans << endl;

  return 0;

}