[白俊]9184号

このように規定規則を有する再帰関数形式の問題が発生し,まず動的プログラミング方式が考えられる.

これまで,解答した動的計画法問題はnに対する認識であった.今回はa,b,cの3つの変数についてですが,問題自体は直感的なので,動的計画法で直接解きます.

−50<=a,b,c<=50であり、入力としての(a,b,c)の総数は約100000であるが、現在の再帰関数の形式では、繰り返し呼び出される(a,b,c)が非常に多くなる.(したがって、これらの問題では通常動的計画法が用いられる)

(a,b,c,)

a or b or cは0->無条件に1を返す.

a or b or c 20->(20,20,20)

を超える

a

残りの

:w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)

再帰呼び出しが発行されても、1を返して再帰呼び出しから返すために、再帰呼び出しのパラメータは「-」のみである.

一般動的計画法によりnをdpソートした.この問題もdp問題ですか?

aまたはbまたはcが0未満の場合は常に1を返すので、実際に入力されたa,b,cがいずれも正の値である場合は、考慮するだけでよい.AND . aまたはbまたはcが20を超える場合は、a=b=c=20の場合と同様であることが多いため、実際に20 x 20 x 20サイズの配列を管理することが考えられる.すなわち,8000種類の場合,先にドアに戻って使用すれば動的プランニング法を用いることができる.

dpの値は0より大きい.フォーマットw(a,b,c−1)+w(a,b−1,c−1)−w(a,b−1,c)およびw(a−1,b,c)+w(a−1,b−1,c)+w(a−1,b,c−1)−w(a−1,b−1,c−1)−w(a−1,b−1,c−1)である.また念のため、for文で出力する場合は確認できます.

#include <iostream>
#include <vector>

int a, b, c;
int dp[21][21][21]; // 각 row의 0번째 column은 사용 x  (a,b,c가 0보다크고 20이하인 경우만을 다룰 것이기에)
					// [a][b][c]


int w(int a, int b, int c)
{
	// 문제 상, dp가 갖는 값은 0이 아닌 값.(확인해봐야함) 
	if (a <= 0 | b <= 0 | c <= 0) return 1;
	else if (a > 20 | b > 20 | c > 20) return w(20,20,20);
	else if (dp[a][b][c]) return dp[a][b][c]; // 이곳에 위치하지 않으면 런타임 에러. dp배열은 0<a,b,c<=20 까지만을 다루고 있기 때문.
	else if (a < b & b < c) return (w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c));
	else return (w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1));
}

int main()
{
	int i, j, k,cnt=1;
	
	for (int i = 1; i < 21; i++) {
		for (j = 1; j < 21; j++) {
			for (k = 1; k < 21; k++) {
				dp[i][j][k] = w(i, j, k);
				
			}
		}
	}
	//a = 50, b = 50, c = 50;
	//printf("w(%d, %d, %d) = %d\n", a, b, c, w(a,b,c));
	///*
	std::cin >> a >> b >> c;
	while (!(a == -1 & b == -1 & c == -1))
	{
		printf("w(%d, %d, %d) = %d\n", a, b, c, w(a,b,c));
		std::cin >> a >> b >> c;
	}
	//*/
	
}

時間を短縮するにはどうすればいいですか?