【伯俊】10835/カードゲーム


# Appreciation

/*
 * Problem :: 10835 / 카드게임
 *
 * Kind :: Dynamic Programming
 *
 * Insight
 * - 이 문제를 Greedy 한 방법으로 풀 수 있을까?
 *   도저히 그렇게 풀 수는 없을 것 같다
 *   + dp[i][j] = 왼쪽 카드를 i개 버리고 오른쪽 카드를 j개 버렸을 때,
 *                남은 카드들로 얻을 수 있는 점수의 최댓값
 *     이라고 하면, dp[i][j] = max(dp[i+1][j], dp[i+1][j+1])
 *     만약, 왼쪽 카드뭉치를 L[N], 오른쪽 카드뭉치를 R[N] 이라고 하면
 *     if (L[i] > R[j]) { dp[i][j] = max(dp[i][j], dp[i][j+1]+R[j] }
 *     # 위처럼 DP 로 풀면 되겠다
 *       -> 우리가 구하고자 하는 값은 위의 dp 정의에 따라 dp[0][0] 이 된다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cstring>

using namespace std;

#define endl '\n'

// Set up : Global Variables
int N;
int L[2000], R[2000];
int dp[2000][2000];

// Set up : Functions Declaration
int f(int l, int r);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    cin >> N;
    for (int i=0; i<N; i++)
        cin >> L[i];
    for (int i=0; i<N; i++)
        cin >> R[i];

    // Process
    /* dp[l][r] = 왼쪽 카드 l개를 버리고 오른쪽 카드를 r개 버렸을 때,
     *            남은 카드들로 얻을 수 있는 점수의 최댓값 */
    memset(dp, -1, sizeof(dp));
    /* 게임을 통해 얻을 수 있는 최종 점수의 최댓값 = dp[0][0] */
    int ans = f(0, 0);

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
int f(int l, int r)
/* 왼쪽 카드 l개를 버리고 오른쪽 카드를 r개 버렸을 때,
 * 남은 카드들로 얻을 수 있는 점수의 최댓값을 반환 */
{
    /* 왼쪽이나 오른쪽 카드들을 모두 버렸다면 더이상 점수를 얻을 수 없음 */
    if (l == N || r == N) return 0;
    if (dp[l][r] != -1) return dp[l][r];
    /* 왼쪽 카드만 버리기, 왼쪽 카드와 오른쪽 카드 둘다 버리기 */
    dp[l][r] = max(f(l+1, r), f(l+1, r+1));
    if (L[l] > R[r]) { /* 왼쪽 카드 > 오른쪽 카드 */
        dp[l][r] = max(dp[l][r], f(l, r+1)+R[r]); /* 오른쪽 카드만 버리기 */
    } return dp[l][r];
}