【POJ-1664】解题报告（递推，dp）

原始题目

放苹果

  • Time Limit: 1000MS
  • Memory Limit: 10000K
  • Total Submissions: 37069
  • Accepted: 22825

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

题目大意

如题

解题思路

  • \(dp[i][j]\) 表示 i 个苹果 j 个盘子的分法。
  • 状态转移： - 当\(i<j\)时，\(dp[i][j]=dp[i][i]\) （不区分盘子，所以盘子多余的情况数和盘子恰好和苹果数相等的情况数相等） - 当\(i\geqslantj\)，\(dp[i][j]=dp[i-j][j]+dp[i][j-1]\) （每个盘子都有苹果和有一个盘子没有苹果两种状况转移） 注意初始的情况就好。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
#include <algorithm>
#include <queue>
#include <map>
#include <string>
#define eps 1e-8
#define INF 0x3f3f3f3f
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
using namespace std;
const int maxn=1e8+2;
typedef long long ll;


ll dp[22][22];
void solve(){
	memset(dp,0,sizeof(dp));
	dp[0][0]=1;
	for(int i=0;i<=21;i++){
		for(int j=0;j<=21;j++){
			if(i==0) dp[i][j]=1;
			else if(j==0) dp[i][j]=0;
			else if(j==1) dp[i][j]=1;
			else {
				if(i<j) dp[i][j]=dp[i][i];
				else dp[i][j]=dp[i][j-1]+dp[i-j][j];

			}
		}
	}
}


int main(){
	int t;
	solve();
	while(cin>>t){
		int m,n;
		rep(i,0,t){
			cin>>m>>n;
			cout<<dp[m][n]<<endl;
		}
	}
}

收获与反思

注意边界情况的考量