Top

(ΦωΦ)<これの答えですよー。目次はここ

---
問1-3
#include <iostream>
#include <algorithm>
using namespace std;

int A, B;
vector<int> a, b;
vector<vector<int>> dp;

// 左の上からi番目か右の上からj番目のどっちを取ろうか悩んでいる状態。
// そのときのすぬけくん(先手)の価値の最大値を返す。
int rec(int i, int j) {
  if(dp[i][j] != -1) { return dp[i][j]; }
  bool isnuke = (i+j) % 2 == 0;
  int res;
  // i==Aかつj==B、つまりどっちももう無い。
  if(i==A && j==B) { res = 0; }
  // 先手の行動
  else if(isnuke) {
    // i==A、つまり左にはもう無い。したがって右の上からj番目を取る。
    if(i==A)      { res = rec(i, j+1) + b[j]; }
    // j==B、つまり右にはもう無い。したがって左の上からi番目を取る。
    else if(j==B) { res = rec(i+1, j) + a[i]; }
    else          { res = max(rec(i+1, j) + a[i],
                              rec(i, j+1) + b[j]); }
  // 後手の行動
  } else {
    // 左にはもう無いので、右の上からj番目を取る。先手には価値は入らない。
    if(i==A)      { res = rec(i, j+1); }
    // 右にはもう無いので、左の上からi番目を取る。先手には価値は入らない。
    else if(j==B) { res = rec(i+1, j); }
    // 後手は先手が不利になるように動く。つまりresが小さくなるように動く。先手には価値は入らない。
    else          { res = min(rec(i+1, j),
                              rec(i, j+1)); }
  }
  return dp[i][j] = res;
}

int main(void) {
  scanf("%d%d", &A, &B);
  dp.assign(1010, vector<int>(1010, -1));
  a.assign(A, 0);
  b.assign(B, 0);
  for(int i=0; i<A; i++) { scanf("%d", &a[i]); }
  for(int i=0; i<B; i++) { scanf("%d", &b[i]); }
  int res = rec(0, 0);
  printf("%d\n", res);
  return 0;
}
    

(ΦωΦ)<おしまい