poj_1664_放苹果.cpp

Problem Links:

poj1664,

Problem:

放苹果

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 16665		Accepted: 10512

Description

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

Input

第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。

Output

对输入的每组数据M和N，用一行输出相应的K。

Sample Input

1
7 3

Sample Output

8

Source

lwx@POJ

Solution:

The idea is from the discussion.
//本题是很简单的递推.
//①最少的盘子放了一个，这样每个盘子至少一个，n个盘子先放上n个，剩下的m-n个可以随便放.
//②最少的盘子没有放，这样剩下的n-1个盘子还是随便放m个.

Source Code:

//Tue Apr 13 16:28:04 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;
//本题是很简单的递推。
//①最少的盘子放了一个，这样每个盘子至少一个，n个盘子先放上n个，剩下的m-n个可以随便放
//②最少的盘子没有放，这样剩下的n-1个盘子还是随便放m个
int apple(int m, int n)
{
    if (m < 0)
        return 0;
    if (m == 0 || n == 1)
        return 1;
    return apple(m, n - 1) + apple(m - n, n);
}

int main(int argc, const char* argv[])
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    int T;
    cin >> T;
    while (T--)
    {
        int M, N;
        cin >> M >> N;
        cout << apple(M, N) << endl;
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}