글 읽기 - 반례가 궁금합니다. (3%에서 틀림)

melon940925 3년 전 0

각 층마다 조합을 구하며 더했습니다.

3%에서 틀린 이유가 뭘까요?..

맞는분 코드랑 여러가지 테스트케이스 넣어보면서 비교해보는데 다 똑같네여.. 어느게 틀린것일지 궁금하네요!

#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 (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);
}

wbjeon2k 3년 전 0

5 6 6 6

ac: 1590

코드: 1842

melon940925 3년 전 0

감사합니다!

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

문제

문제

출처

ICPC

반례가 궁금합니다. (3%에서 틀림)

melon940925 3년 전 0

wbjeon2k 3년 전 0

melon940925 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말