-3

説明：

ある日、トンボはチョコレートをn個受け取ります。彼のm人の友人にチョコレートを配布することに決めたので、彼は次のルールを考え出しました。

  • まず、友情の親密さに基づいて、友達を1からmまでランク付けします。

  • 次に、ランクiの友達がx個のチョコレート（so F[i]=x）を取得した場合、の友達はx個以上のチョコレート（ so）x+1を取得する必要があります。ここで、は正の数です。x+kx <= F[i+1] <= x +kk

  • 位置1の友人はk個以上のチョコレートを手に入れるべきではありません（そうF[1] <= k）

  • 一部の友人はチョコレートをゼロにするかもしれません。

  • 可能であれば、トンボにはチョコレートを入れないでください。彼は歯痛があり、キャンディーを食べるべきではありません。

数学に精通していませんが、トンボはすべてのチョコレートを配布する方法の数を知りたがっています。だから彼はあなたの助けを求めています

入力：

入力ファイルは、それぞれが1つのケースを定義する一連の入力行で構成されます。各ケースの入力は、3つの正の整数の1行です。

N (1 <= n <= 500), m (1 <= m <= 100), k (1 <= k <= 100).

入力ファイルはで終了し0 0 0ます。

出力：

それぞれの場合について、すべてのチョコレートを1行に分配できる方法の数を出力します。

サンプル入力：

1 1 1
4 2 2
5 3 2
0 0 0

出力：

1 
2
3

元のページ：http ：//acm.whu.edu.cn/learn/problem/detail？problem_id = 1031

再帰的な方法を試しましたが、制限時間を超えました。次に、再帰をキューに置き換えようとしましたが、メモリ制限を超えました。この問題は動的計画法に関するものですか？誰かが私にヒントを与えることができますか？

4

1 に答える 1

1

resursiveメソッドに剪定を追加しようとしましたか？すなわち。制限のために残りのキャンディーを残りの友達に配布できない場合は、それを止めることができます。

また、uはDPメソッドを使用できます。f [i] [j] [k]は、最初のi人の友達、j人のキャンディーを持っているi人目の友達、残りのk人のキャンディーに配布した可能性のある方法の数を意味します。

boundary: f[0][0][n]=1;
u can use forward recurrence:
f[i+1][j+l][k-(j+l)]+=f[i][j][k]; 0<=l<=K (K here is what in your input)
the final answer is sum(0<=i<=n)(f[m][i][0])
于 2013-01-27T02:09:05.507 に答える