[白俊C+]2775女性会長になる

質問する

普段からクラス会に参加するのが好きな朱熹は、この機会に女性会長になり、各階層の人を集めてクラス会を組織しようとした.
このアパートに住むには条件があり、「a階のb番に住むには、自分の下(a-1)階の1番からb番までの人数で、人を連れて帰って住む」という契約条項を守らなければならない.
アパートに空き家がないと仮定し、すべての住民がこの契約条件を守ったとすると、与えられた正の整数kとnに対して、k階印刷n号に何人が住んでいるのか.しかし、マンションは0階から、各階は1番から、0階のi号はi名である.

入力

最初の行はTestcaseの数Tを与える.そして、それぞれの場合、1行目の整数k、2行目の整数nを入力する

しゅつりょく

各テストケースについて、その家の世帯数を印刷してください.
https://www.acmicpc.net/problem/2775

に答える

DPの問題は久しぶりです通常DPは、任意の初期値により連続的な点火式により所望の値を求める方法である.
注記はメモリに記録され、各コーナーとコーナー全体に値が必要になります.
メモリからの取り出しと書き込みの過程を加えて、解答を行いました.

各階の部屋は図のように、人員が住んでいる場合、dpを右側にすることができます.
この場合、基準を上にする方法により、初期値をdp[0][1]~dp[0][n]とすることができるので、問題が容易になる.
DPの関数を求めます.このフロアこの部屋の人員は、1つの部屋の下部でナビゲーションする必要があります.
1番~n番の和をsum変数に加える、
このとき、すべてのdpアレイの初期値は-1であるため、この層、部屋のdp値を解くと、
配列から取り出して書き込みます.そうしないと、
この層は、部屋dp値を求めるDP関数を再帰的に呼び出している.
これは、求和をメモリに格納し、同時に返す必要があるため重要です.

この部分ではdp[k][n]!=-1、メモの形式を利用して、それを出して書きます.
メモのフォーマットを利用してこそ、時間を効率的に短縮することができます.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
int dp[15][15]; //0층~14층 : 1호~14호

int DP(int k, int n) {
	if (k == 0) return n; //0층 i호에는 i명이 산다

	int sum = 0;
	//메모이제이션과 재귀를 통해 k-1층의 1~n호실까지합을 구함
	for (int i = 1; i <= n; i++) { 
		if (dp[k - 1][i] != -1)
			sum += dp[k - 1][i]; //이미있으면 꺼내씀
		else
			sum += DP(k - 1, i); //재귀적호출
	}
	//구한 합을 저장
	dp[k][n] = sum; 
	return sum;
}

int main(int t, int k, int n) {
	scanf("%d", &t);
	for (int i = 0; i < 15; i++) for (int j = 0; j < 15; j++) dp[i][j] = -1; //초기화
	for (int i = 1; i <= 14; i++) dp[0][i] = i; //0층 i호에는 i명이산다.
	while (t--) {
		scanf("%d%d", &k, &n);
		if (dp[k][n] != -1) { //이미 찾은값이면
			printf("%d\n", dp[k][n]);
			continue;
		}

		printf("%d\n", DP(k, n));
	}


	return 0;
}