-3

描述：

有一天，蜻蜓收到了 n 块巧克力。在决定将巧克力分发给他的 m 个朋友后，他提出了以下规则：

  • 首先，他将根据友谊的亲密程度从 1 到 m 对他的朋友进行排名

  • 其次，如果等级 i 的朋友得到 x 个巧克力（so F[i]=x），那么第 i 位的朋友x+1应该得到不少于 x 个巧克力并且不超过x+k巧克力（so x <= F[i+1] <= x +k），其中k是一个正数。

  • 位置一的朋友不应该得到超过k个巧克力（所以F[1] <= k）

  • 有些朋友可能会得到零巧克力。

  • 如果可能的话，蜻蜓应该没有巧克力。他牙痛，不应该吃糖果。

虽然不精通数学，但蜻蜓渴望知道所有巧克力的分发方式有多少。所以他在寻求你的帮助

输入：

输入文件由一系列输入行组成，每行定义一个案例。每种情况的输入是一行三个正整数：

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

输入文件将由0 0 0.

输出：

对于每种情况，输出所有巧克力可以在一行上分布的方式数。

样本输入：

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

您是否尝试在递归方法中添加一些修剪？IE。如果由于限制无法将剩余的糖果分发给其他朋友，您可以停止。

你也可以使用DP方法。令 f[i][j][k] 表示为前 i 个朋友分发的可能方式数，第 i 个朋友有 j 个糖果，还有 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 回答