글 읽기 - 해결하였는데 궁금한 점이 있습니다.

melon940925 3년 전 0

dfs함수에서

if (red < 0 || blue < 0 || green < 0)return 0;

이 부분이 없으면 왜 틀렸는지가 궁금합니다.

애초에 재귀호출을 할 때, red와 green blue가 0밑으로 안가게끔 조건을 정해놨는데 왜 그런것인가요?!

#include <bits/stdc++.h>

using namespace std;
#define endl '\n'
typedef long long ll;
ll N, red, green, blue;

ll dp[11][101][101][101];


ll dfs(ll k, ll red, ll green, ll blue) {
	if (red < 0 || blue < 0 || green < 0)return 0;
	if (k > N)return 1;
	ll& ret = dp[k][red][green][blue];
	if (ret != -1)return ret;
	ret = 0;
	ll times = k;
	ll temp = k;
	while (--temp) times *= temp;
	if (k % 3 == 0) {
		ll T = k / 3;
		temp = k / 3;
		while (--temp)T *= temp;
		T = times / (T * T * T);
		if (red >= k / 3 && green >= k / 3 && blue >= k / 3) {
			ret += dfs(k + 1, red - k / 3, green - k / 3, blue - k / 3) * T;
		}
	}
	if (k % 2 == 0) {
		ll T = k / 2;
		temp = k / 2;
		while (--temp)T *= temp;
		T = times / (T * T);
		if (red >= 2 / k && green >= 2 / k) {
			ret += dfs(k + 1, red - k / 2, green - k / 2, blue) * T;
		}
		if (red >= 2 / k && blue >= 2 / k) {
			ret += dfs(k + 1, red - k / 2, green, blue - k / 2) * T;
		}
		if(green>=2/k&&blue>=2/k){
			ret += dfs(k + 1, red, green - k / 2, blue - k / 2) * T;
		}
	}
	if (red >= k)ret += dfs(k + 1, red - k, green, blue);
	if (green >= k)ret += dfs(k + 1, red, green - k, blue);
	if (blue >= k)ret += dfs(k + 1, red, green, blue - k);
	return ret;
}


int main() {
		cin >> N >> red >> green >> blue;
		memset(dp, -1, sizeof(dp));
		cout << dfs(1, red, green, blue);
}

newdeal 3년 전 0

34줄부터 40줄까지의 조건문이( >= 2/k ) 같이 되어있어서 그런것 같네요.

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

문제

문제

출처

ICPC

해결하였는데 궁금한 점이 있습니다.

melon940925 3년 전 0

newdeal 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말