10835번: 카드게임

https://www.acmicpc.net/problem/10835


$O(n^2)$

dp[i][j]: 왼쪽 더미에 i번째 카드, 오른쪽 더미에 j번째 카드가 보일 때, 이후 얻을 수 있는 최대 점수

#include<cstdio>
#include<algorithm>
using namespace std;
int a[2001], b[2001], n, dp[2001][2001], ck[2001][2001];
int f(int x, int y) {
    if (x > n || y > n) return 0;
    if (!ck[x][y]) {
        ck[x][y] = 1;
        dp[x][y] = a[x] > b[y] ? f(x, y + 1) + b[y] : max(f(x + 1, y), f(x + 1, y + 1));
    }
    return dp[x][y];
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    for (int i = 1; i <= n; i++) scanf("%d", b + i);
    printf("%d", f(1, 1));
    return 0;
}