티스토리 뷰

알고리즘 관련/BOJ

BOJ)10835 카드게임

JASON 자손9319 2017. 3. 23. 16:12

문제: 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]) 라는 점화식을 통하여 문제를 해결할 수 있다.


 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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, -1sizeof(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(00));
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)1755 숫자놀이  (0) 2017.03.23
BOJ)1747 소수&팰린드롬  (0) 2017.03.23
BOJ)10835 카드게임  (0) 2017.03.23
BOJ)7535 A Bug's Life  (0) 2017.03.22
BOJ)3747 완벽한 선거!  (0) 2017.03.22
BOJ)8992 집기 게임  (0) 2017.03.20
댓글
댓글쓰기 폼