PKU Judge Online 1664 放苹果

■1664 放苹果

□Problem
m個のリンゴをn皿に分配する．分配の仕方は何通りあるかを求めよ．
m=7，n=3の時は，
7 0 0
6 1 0
5 2 0
5 1 1
4 3 0
4 2 1
3 3 1
3 2 2
の8種類．

□Solution
f(m,n,e)
m個のリンゴをn皿に分配する組．ただしそれぞれの皿のリンゴはe個以下とする．
f(0,0,e)=1
…0個のリンゴを0皿に分配する方法は1通り
f(m,0,e)=0 (m>0)
…1個以上のリンゴを0皿には分配できない
f(m,n,e)=Σ_{i=[i,min(m,e)]}f(m-i,n-1,min(i,e))
…まず1つの皿にリンゴを置く，その際，置けるリンゴの個数iは，[1,min(m,e)]まで．
そしてリンゴをi個置いたら，残りn-1皿にはm-i個のリンゴを置くことになるが，それぞれの皿のリンゴの個数の上限は，min(i,e)となる．
上の式より，再帰的に求める(mとnが与えられたらf(m,n,m)を呼び出せばよい)．

□Code

package p1664;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

    Scanner sc=new Scanner(System.in);

    final int INF=Integer.MAX_VALUE;
    final double EPS=1e-9;

    void run(){
        for(int t=sc.nextInt(); t>0; t--){
            int m=sc.nextInt();
            int n=sc.nextInt();
            println(""+f(m, n, m));
        }
    }

    // m個のリンゴをn皿に分配する
    // ただしそれぞれの皿のリンゴはe個以下
    int f(int m, int n, int e){
        if(n==0)
            return m==0?1:0;
        int ret=0;
        // ある皿に置けるリンゴの個数iは，0<=1<=min(m(上限), e(制約))
        // ある皿にリンゴをi個置くと，m-i個のリンゴを残りn-1皿に分配することになる
        // ただしそれぞれの皿のリンゴはmin(i(上限), e(制約))個以下
        for(int i=0; i<=Math.min(m, e); i++)
            ret+=f(m-i, n-1, Math.min(i, e));
        return ret;
    }

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    public static void main(String[] args){
        // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
        new Main().run();
    }
}