Top

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

---
問2-5
#include <iostream>
#include <algorithm>
using namespace std;

int main(void) {
  int A, B; scanf("%d%d", &A, &B);
  vector<int> a(A), b(B);
  for(int i=0; i<A; i++) { scanf("%d", &a[i]); }
  for(int i=0; i<B; i++) { scanf("%d", &b[i]); }
  // 左の上からi番目、右の上からj番目のどっちを取るか悩んでいる状態。
  // そのときの先手の価値の最大値を覚えておく。
  vector<vector<int>> dp(1010, vector<int>(1010));
  // ループの中ではdpテーブルはiもjも大きいほうから小さいほうへと値を渡しているので、
  // その順序でループを回すようにする。
  for(int i=A; i>=0; i--) {
    for(int j=B; j>=0; j--) {
      if(i==A && j==B) { continue; }
      bool isnuke = (i+j) % 2 == 0;
      if(isnuke) {
        if(i==A)      { dp[i][j] = dp[i][j+1] + b[j]; }
        else if(j==B) { dp[i][j] = dp[i+1][j] + a[i]; }
        else          { dp[i][j] = max(dp[i+1][j] + a[i],
                                       dp[i][j+1] + b[j]); }
      } else {
        if(i==A)      { dp[i][j] = dp[i][j+1]; }
        else if(j==B) { dp[i][j] = dp[i+1][j]; }
        else          { dp[i][j] = min(dp[i+1][j],
                                       dp[i][j+1]); }
      }
    }
  }
  int res = dp[0][0];
  printf("%d\n", res);
  return 0;
}
    

(ΦωΦ)<おしまい