这道题卡住了，求大家帮忙看看，或者提供下思路,该怎么处理

这道题卡住了，求大家帮忙看看，或者提供下思路
有一天，Lolita上街买菜，在她要买鸡蛋的时候，忽然盯着几个篮子发呆。
她在想，如果把手中的鸡蛋都放到这几个篮子里，有多少种放法呢？
她想了很久，但想不出来应该怎么算，你们能帮帮她吗？

输入：
多组数据，每一组是一行，一行有两个数e,b，e是鸡蛋数目(1<=e<=1000)，b是篮子数目(1<=b<=100)。

输出：
对每一组数据算出总放法数目并输出，要单独占一行。题目数据保证最后计算结果小于1e19

样例输入：
8 1
8 2
6 3
7 3

样例输出：
1
5
7
8

提示：
6 3的话，可以是
0+0+6
0+1+5
0+2+4
0+3+3
1+1+4
1+2+3
2+2+2
共7种方法

C/C++ code

#include <iostream>#include <set>int count = 0;using namespace std;void putegg(int egg, int basket);void main(){    int basket;     int egg;    cin >> egg;    cin >> basket;    putegg(egg, basket);    cout << count << endl;    }void putegg(int egg, int basket){    if (egg < 0 || basket < 0)    {        return;    }    else if (egg == 0 && basket == 0)    {        ++count;        return;    }    else    {        for (int i = 0; i <= egg; ++i)//用递归遍历所有出现的可能        {            //set<int> rec;            int tegg = egg - i;            int tbasket = basket - 1;            //rec.insert(tegg);                     putegg(tegg, tbasket);        }    }}

[解决办法]
由代码可知是动态规划题目

探讨

这个看不懂

C/C++ code

#include<stdio.h>

_int64 dp[101][1001];

void init();

int main()
{
int n, m;
init();

while(scanf("%d %d", &amp;n, &amp;m)!=EOF)
{
……

[解决办法]
for (int i = egg>limit?limit:egg; i >= (egg-i)/(basket-1); --i)
让i从本次递归里允许的最大值开始，直到等于下一次递归所能允许的最小限额为止进行循环。

如果剩下的蛋在剩下的篮子里平分之后都还比i大，那显然是没法保证后面的递归符合不重复的原则了。因为要保证不重复就得保证后面的篮子里不会有比前面的篮子更多的鸡蛋。
[解决办法]
好像那个循环终止条件有问题......整数除法会丢掉余数，特定的数字下可能导致i过小。
[解决办法]
for (int i = egg>limit?limit:egg; i >= (egg-i+basket-2)/(basket-1); --i)
[解决办法]
简化一下：

C/C++ code

for (int i = egg>limit?limit:egg; i*basket >= egg; --i)
[解决办法]
在网上搜索动态规划，DP之类的，能看到很多资料。动态规划稍微的学学很容易，应用也很简单。用来计算各种组合爆炸的问题超级强大。

超出数据范围了就只有用自己写的大数方式了，到博客区一搜一大堆。 

 

查看更多 下一篇