글 읽기 - 카드게임(dp) 어디 부분이 틀린지 모르겠네요

lyzqm 6년 전 0

dp[l][r] : 왼쪽에 l장, 오른쪽에 r장 쌓여있을 때 얻을 수 있는 최대 점수

A[l] : 왼쪽 l장번째 카드 , B[r] :오른쪽 r장번째 카드

plus : 누적 점수

8 4

9 7

-> 0

1 4

3 2

->5

어디부분을 빼먹은걸까요?

#include <cstdio>
#include <algorithm>
using namespace std;
int N, L, R;
int A[2001], B[2001];
int dp[2003][2003];
int loop(int l, int r, int plus){
	int a = 0, b, c;
	if (r == N + 1 || l == N + 1)
		return plus;

	if (dp[l][r] != -1)
		return dp[l][r];
	dp[l][r] = max(dp[l][r], plus);

	if (A[l] > B[r])
		a = loop(l, r + 1, plus + B[r]);
	b = loop(l + 1, r, plus);
	c = loop(l + 1, r + 1, plus);

	dp[l][r] = max(max(dp[l][r], a), max(b, c));
	return dp[l][r];
}
int main(){
	scanf("%d", &N);
	for (int n = 1; n <= N; n++)
		scanf("%d", &A[n]);
	for (int n = 1; n <= N; n++)
		scanf("%d", &B[n]);
	for (int n = 1; n <= N; n++)
		for (int m = 1; m <= N; m++)
			dp[n][m] = -1;
	printf("%d\n", loop(1, 1, 0));
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

카드게임(dp) 어디 부분이 틀린지 모르겠네요

lyzqm 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말