[DP(Top-Down)] 백준 10835 카드게임 C++

코딩테스트/동적계획법

[DP(Top-Down)] 백준 10835 카드게임 C++

유(YOO) 2023. 9. 4. 16:26

10835번: 카드게임

첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오

www.acmicpc.net

#include <iostream>
#include <vector>
#define N 2001

using namespace std;

int n;
vector<int> l(N, 0);
vector<int> r(N, 0);
int dp[N][N];

int func(int s, int e) {
    int& ret = dp[s][e];
    if (ret != -1) return ret;
    if ((s >= n) || (e >= n)) return 0;

    ret = 0;
    if (l[s] > r[e]) ret = max(max(func(s+1, e), func(s+1, e+1)), func(s, e+1) + r[e]);
    else ret = max(func(s+1, e), func(s+1, e+1));

    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n;

    for(int i=0; i<n; i++) cin >> l[i];
    for(int i=0; i<n; i++) cin >> r[i];

    fill(&dp[0][0], &dp[N-1][N], -1);
    cout << func(0, 0);

    return 0;
}