UVa 12484 : Cards

問題リンク : https://uva.onlinejudge.org/external/124/p12484.pdf

問題概要 :
整数の書かれたN枚のカードが一直線上に並んでいる
AさんとBさんは交互にカードを取っていく
ただし、カードを取る際は両端のうちどちらかでないといけない
最初にAさんがカードを取る
Aさんの目的は取ったカードに書かれている整数の和を最大化することであり、
Bさんの目的はAさんが取ったカードにかかれている整数の和を最小化することである
このとき、Aさんが得られるカードにかかれている整数の和の最大値はいくらか？

解法 :
動的計画法であった
カードが１枚のとき、カードが２枚のとき、...、カードがN枚のとき、といった感じでDPしていく
dp[i枚のカード][左からj番目] := 左からj番目のカードからi枚のカード列でAさんが得られる最大値

そのまま配列を確保すると10^8になるのでiは偶奇で使い分ける

https://cerc.tcs.uj.edu.pl/2014/data/l.pdf
上の問題と発想が似ているような気がした

[追記]
例えば、サンプルの３つめを考えてみる
[ 47 50 -3 7 ]
まず、長さが１の場合は
[47] と [50] と [-3] と [7]
長さが2の場合は
[47 50] [50 -3] [-3 7]
長さが3の場合は
[47 50 -3] [50 -3 7]
長さが4の場合は
[47 50 -3 7]

これらの状態について、カードの枚数が少ないほうからDPしていく
遷移の際には、 j 番目のカードを取るか、 j+長さ-1番目(j番目を最も左として長さiのときの右)のカードを取るのか　どちらか

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;
const ll LLINF = LLONG_MAX;
int N;
ll arr[10010],dp[2][10010];

int main(){
  while( cin >> N ){
    rep(i,N) cin >> arr[i];
    rep(i,2) rep(j,N+1) dp[i][j] = 0;
    REP(length,1,N+1) {
      for(int left = 0; left + length - 1 < N; left++ ){
	if( !( length & 1 ) ) dp[length&1][left] = max(dp[!(length&1)][left]+arr[left+length-1],dp[!(length&1)][left+1]+arr[left]);
	else                  dp[length&1][left] = min(dp[!(length&1)][left],(left+1<N)?dp[!(length&1)][left+1]:0);
      }
    }
    cout << dp[0][0] << endl;
  }
  return 0;
}