POJ1664总结

放苹果

题目来源

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

我的代码

这题虽然是一个整数拆分的模板题，但是我发现我的思路和网上的朋友们给出的想法不太一样。

我的思路是dp[i][j]的j是所需要的盘子个数，每种情况下给定多少盘中就必须全部用到。那么最后的情况就是所有不同的盘子使用数量的情况之和。dp方程是dp[i][j]=dp[i-1][j-1]+dp[i-j][j]，意思是i个苹果放j个盘子里面的情况分为两种：一种是j个盘子中存在一个盘子只有一个苹果的，这种情况相当于去掉这个盘子和中国苹果dp[i-1][j-1]；第二种情况是所有盘子的苹果数量都大于1，那么每一个盘子去掉一个苹果之后肯定至少还剩下一个苹果dp[i-j][j]。

#include<stdio.h>

int main()
{
	int t,m,n;
	scanf("%d",&t);
	while (t--)
	{
		int dp[11][11]={0};
		int ans=0;
		scanf("%d%d",&m,&n);
		for (int i=1;i<=m;i++)
		{
			for (int j=1;j<=i;j++)
			{
				if (i == 1) dp[i][j] = 1;
	            else if (j == 1) dp[i][j] = 1;
	            else if (i==j) dp[i][j]=1;
				else
				{
					dp[i][j]=dp[i-1][j-1];
					if (i>=2*j) dp[i][j]+=dp[i-j][j];
				}
			}
		}
		for (int j=1;j<=n;j++) ans+=dp[m][j];
		printf("%d\n",ans); 
	}
	return 0;
}

网上的解法如下，这一种做法的j是指任意一个盘子内最大的苹果数：

#include<bits/stdc++.h>
using namespace std;
int main() {
	int n, k;
	while (~scanf("%d%d", &n, &k)) {
		int dp[200][200];
		int i, j;
		for (i = 1; i <= n; i++) {
			for (j = 1; j <= k; j++) {
				if (j == 1 || i == 1)
					dp[i][j] = 1;
				else if (j == i) {
					dp[i][j] = dp[i][j - 1] + 1;
				}
				else if (i < j) {
					dp[i][j] = dp[i][i];
				}
				else if (i > j) {
					dp[i][j] = dp[i][j - 1] + dp[i - j][j];
				}
			}
		}
		printf("%d\n", dp[n][k]);
	}
	return 0;
}

反思

划分子问题的方式很重要。