글 읽기 - 해당 문제 bottom-up approach 조언 부탁드립니다.

amatuer789 5년 전 0

top-down은 구현이 되는데, bottom-up이 계속 틀리네요.

dp[i][j] : 왼쪽 카드 i번, 오른쪽 카드 j 번까지 사용했을 때, 최대 값으로 set 하고,

오른쪽 카드가 더 작은 경우 있을 떄, max 계산에 포함 시켰습니다.

#include <cstdio>
#define max(a,b,c) ((a)<(b)?(b>c?b:c):(a>c?a:c))
using namespace std;
int n, i, j, v, ans;
int A[2001], B[2001];
int dp[2002][2002];
int main(){
    scanf("%d", &n);
    for(i = 1; i <= n; i++)
        scanf("%d", A+i);
    for(i = 1; i <= n; i++)
        scanf("%d", B+i);
    for(i = 1; i <= n+1; i++){
        for(j = 1; j <= n+1; j++){
            if(A[i] > B[j-1]) v = dp[i][j-1]+B[j-1];
            else v = -1;
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], v);
            ans = max(ans, dp[i][j], -1);
        }
    }
    printf("%d", ans);
}

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

문제

문제

출처

ICPC

해당 문제 bottom-up approach 조언 부탁드립니다.

amatuer789 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말