[KOI] 백준 10835 - 카드게임

www.acmicpc.net/problem/10835

 

다음 가지치기로 얻을 수 있는 최대 점수를 동적계획법으로 구하면 된다.

 

왼쪽 카드를 버렸을 때 / 양쪽 카드를 버렸을 때 / 오른쪽 카드를 버릴 수 있을 경우 버리고 점수를 얻었을 때

 

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
 
int n;
int l[2000], r[2000];
int dp[2000][2000];
 
int memo(int ldx, int rdx);
 
int main()
{
    memset(dp, -1, sizeof dp);
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> n;
 
    for (int i = 0; i < n; ++i)
        cin >> l[i];
    for (int i = 0; i < n; ++i)
        cin >> r[i];
    
    cout << memo(0, 0);
}
 
int memo(int ldx, int rdx)
{
    if (ldx == n || rdx == n)
        return 0;
    
    int &ret = dp[ldx][rdx];
 
    if (ret != -1)
        return ret;
    
    ret = max(memo(ldx + 1, rdx + 1), memo(ldx + 1, rdx));
    if (l[ldx] > r[rdx])
        ret = max(ret, r[rdx] + memo(ldx, rdx + 1));
    return ret;
}