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