小编Mil*_*Man的帖子

前段时间,我正在研究编程问题(CCC).我在过去的比赛中也遇到过类似的问题所以我决定问一下这个问题.问题基本上就是这个.

给你n个人和p个馅饼.

人们站成一排.

你必须在其中分发p个馅饼.你按顺序进行,每个人必须至少收到与他们之前一样多的棋子.每个人必须至少收到一块馅饼,不得留下任何馅饼.

您必须返回分发饼图的可能方式的数量.

我设法创建了以下递归解决方案,但以下输入需要太长时间(超过5秒):

120件,20人 - > 97132873

250件,130人 - > 1844349560

我的解决方案

import java.io.*;

public class Main
{
  int pieces, people;
  int combinations = 0;

  public void calculate (int person, int piecesLeft, int prev)
  {
    if (person == people)
    {
        if (piecesLeft == 0)
            combinations++;              
    }
    else
    {
        for (int x = prev ; (x * (people - person)) <= piecesLeft ; x++)
        {
            calculate (person + 1, piecesLeft - x, x);
        }
    }
  }


  public static …