[Baekjoon]225号を合わせてcpp

7239 ワード
baekjoon テキストリンク
[白俊]225号合分解題リンク
DPはなかなか解けない.だんだん慣れてきたようですが、なかなか難しいです.

・主なアイデア


この問題は「何個の数字」で「どの数字」の数を表す問題です.このためにこの階層配列を使用しました.dp[num][count]の形式で、numは生成を必要とする数字であり、countはnumを生成するための数字である.
つまり、dp[4][k]であれば、「4以下のk個の数字を利用して4を作る数」を意味する.k個の数字を用いて4を生成する方法は以下の通りである.便宜上、「n以下の数字」の表現は省略する.
まず4を作り4以下の数字だけを使います.したがって、以下の場合に4を作成することができる.
0 + 4
1 + 3
2 + 2
3 + 1
4 + 0
問題にはゼロを含めることができます.上記の5つの場合、プラス記号の左側の数字は「k-1個の数字」であり、プラス記号の右側の数字は新しく追加された1個の数字である.つまり、プラス記号の左右の数字は全部でk個の数字で表示されます.
すなわち、それぞれの場合において、すべての数字を加えた値が「k個の数字n」である場合の数である.この内容に基づいて、k個の数字を用いてnを作成する場合、nの数を求めるには、以下の論理が必要である.
  • nを生成するには、0からn-1までのすべての数値が必要です.
  • kの数値を使用して特定の数値tempを作成すると、(k-1개로 0을 만드는 경우의 수) ~ (k-1개로 temp를 만드는 경우의 수)の和.
    • この機能を実装するソースコードの全文は次のとおりです.
    #include <iostream>

int n, k;
long long dp[201][201] = { 0, };

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> n >> k;

	for (int count = 0; count <= n; count++) {
		dp[count][1] += 1;
		for (int numCnt = 1; numCnt < k; numCnt++) {
			for (int temp = 0; temp <= count; temp++) {
				if (dp[count - temp][numCnt] > 0) {
					dp[count][numCnt + 1] = (dp[count][numCnt + 1] + dp[count - temp][numCnt]) % 1000000000;
				}
			}
		}
	}

	std::cout << dp[n][k];
}
    [JS]JavaScript中級教程(feat.コード鞍馬)-call、apply、bind
    イベントの処理