BOJ)10835 카드게임

문제: icpc.me/10835

오른쪽 카드를 버릴 때 점수를 얻을 수 있을 때 얻을 수 있는 최고 점수를 구하는 문제이다,

dp[x][y] <- 왼쪽 카드가 x장 남고 오른쪽 카드가 y장 남았을 때 얻을 수 있는 최고 점수

라고 정의한 뒤 dp[x][y]= max(dp[x+1][y],dp[x+1][y+1]) if(a[x]>b[y]) dp[x][y]=max(dp[x][y],dp[x][y+1]+b[y]) 라는 점화식을 통하여 문제를 해결할 수 있다.

 

#include <cstdio>
#include <algorithm>
#include <cstring>
#define INF 987654321
using namespace std;
int dp[2001][2001], n, a[2001], b[2001];
int func(int x, int y) {
    if (x == n || y == n)return 0;
    int &ret = dp[x][y];
    if (ret != -1)return ret;
    ret = max(func(x + 1, y), func(x + 1, y + 1));
    if (a[x] > b[y])
        ret = max(ret, func(x, y + 1) + b[y]);
    return ret;
}
int main() {
    memset(dp, -1, sizeof(dp));
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    for (int j = 0; j < n; j++)
        scanf("%d", &b[j]);
    printf("%d\n", func(0, 0));
    return 0;
}