[10835] 카드게임

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

10835번: 카드게임

<문제>

대소관계에 의해서 분기는 총 3가지로 갈라진다. O(N^2)의 탑다운dp로 구현했으며,

하나의 상태는 왼쪽 카드 더미와 오른쪽 카드 더미를 각각 몇개사용했는지로 구분된다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, a[2001], b[2001], dp[2001][2001];
int f(int l, int r) {
    if (l == n || r == n) return 0;
    if (dp[l][r] != -1) return dp[l][r];
    if (a[l] > b[r]) dp[l][r] = max(b[r] + f(l, r + 1), dp[l][r]);
    dp[l][r] = max({f(l + 1, r), f(l + 1, r + 1), dp[l][r]});
    return dp[l][r];
}
int main(void) {
    memset(dp, -1, sizeof(dp));
    cin >> n;
    int i;
    for (i = 0; i < n; i++) cin >> a[i];
    for (i = 0; i < n; i++) cin >> b[i];
    cout << f(0, 0);
    return 0;
}