(ΦωΦ)<これの答えですよー。目次はここ。
---
問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;
}
(ΦωΦ)<おしまい