글 읽기 - 탑-다운으로 짰는데 뭐가 문제일까요?

pwr2011 4년 전 0

dp를 탑-다운으로 풀다가 안되서 다른분들껄 봤는데 다 바텀-업으로 푸셨더라고요....

탑-다운방식에 무슨 문제가 있을까요? 테케는 다 맞습니다.

#include<iostream>
#include<algorithm>
#include<cstring>

#define MAX_NUM -100000000
#define MAX_N 1005

using namespace std;

int card_val[1005]; 
int dp[1005][1005];
int n;

int cal_card(int idx, int money,int leaved) { //number is the number of buy

	if (dp[idx][leaved] != -1) {

		return dp[idx][leaved];
	}

	if (idx == n) {
		if (leaved == 0)
			dp[idx][leaved] = money;
		else
			dp[idx][leaved] = MAX_NUM;
		return dp[idx][leaved];
	}

	if (leaved == 0) {
		dp[idx][leaved] = money;
		return dp[idx][leaved];
	}

	int tmp = cal_card(idx + 1, money, leaved);

	int tmp2 = -1;
	if (leaved - (idx + 1) >= 0) {
		tmp2 = cal_card(idx, money + card_val[idx], leaved - (idx + 1));
	}
	if (tmp < tmp2) dp[idx][leaved] = tmp2;
	return dp[idx][leaved];
}

int main()
{
	memset(dp, -1, 1005 * 1005 * sizeof(int));
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> card_val[i];
	}

	int answer = cal_card(0, 0,n);

	cout << answer;
}

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

문제

문제

출처

ICPC

탑-다운으로 짰는데 뭐가 문제일까요?

pwr2011 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말