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

view plainprint?

1. package p1664;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6. import java.io.*;  
7.   
8. import static java.lang.Math.*;  
9. import static java.util.Arrays.*;  
10.   
11. public class Main{  
12.   
13.     Scanner sc=new Scanner(System.in);  
14.   
15.     final int INF=Integer.MAX_VALUE;  
16.     final double EPS=1e-9;  
17.   
18.     void run(){  
19.         for(int t=sc.nextInt(); t>0; t--){  
20.             int m=sc.nextInt();  
21.             int n=sc.nextInt();  
22.             println(""+f(m, n, m));  
23.         }  
24.     }  
25.   
26.     // m個のリンゴをn皿に分配する  
27.     // ただしそれぞれの皿のリンゴはe個以下  
28.     int f(int m, int n, int e){  
29.         if(n==0)  
30.             return m==0?1:0;  
31.         int ret=0;  
32.         // ある皿に置けるリンゴの個数iは，0<=1<=min(m(上限), e(制約))  
33.         // ある皿にリンゴをi個置くと，m-i個のリンゴを残りn-1皿に分配することになる  
34.         // ただしそれぞれの皿のリンゴはmin(i(上限), e(制約))個以下  
35.         for(int i=0; i<=Math.min(m, e); i++)  
36.             ret+=f(m-i, n-1, Math.min(i, e));  
37.         return ret;  
38.     }  
39.   
40.     void print(String s){  
41.         System.out.print(s);  
42.     }  
43.   
44.     void println(String s){  
45.         System.out.println(s);  
46.     }  
47.   
48.     public static void main(String[] args){  
49.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
50.         new Main().run();  
51.     }  
52. }  

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();
    }
}