NYOJ 整数划分(三) (划分数大集合)

第六行： 打印一个空行

将n划分成若干个正整数之和： 
我们设dp[i][j]表示的是，当前的数字是i，且最大的划分是j的时候的划分数
初始化：dp[][1] = 1, dp[1][] = 1 , 当一个数的最大划分是1的时候也就是他全部都是1，或者当前数字是1的时候只能由一种划分
转移方程：

  dp[i][j] = dp[i][j-1] + dp[i-j][j](i>=j) 
   dp[i][j] = dp[i][i] (i<j) 
解释一下这个转移方程，当前数字为i最大划分是j可以由当前数字为i最大划分为j-1转换过来，（4,3） {1,3},{2,2}, (4,2) {1,2,1,},{2,2}是吧其实就是等于把那个大的在划分一下，还可以由i-j 和 j转移过来 (6,3) {3,3} (9,3) {3,3,3},其实就是前一个状态在加上一个j得来的。大概就是这个意思把。
(二)
将n划分成k个正整数之和的划分数(这个其实就是给你n个苹果和m个盘子而且盘子不能为空，问你最多有多少种分发)
我们设dp[i][j] 表示的是 当前还剩下n个苹果和m个盘子的时候的最大值
初始化： dp[][1] = 1,当他只剩下一个盘子的时候，就只有一种分法。
状态转移方程：
dp[i][j] = dp[i-j][j] + dp[i-1][j-1] (i>=j) 


解释一下这个转移方程，你剩下i个苹果m个盘子的时候，那么下一次你放的时候，可以在每个盘子里都放一个苹果，他的转移方程就是dp[i-j][i],当前剩下i-j个苹果（因为每个盘子都放了一个，总共有j个盘子，之后盘子数量还是那么多）或者你只在一个盘子里面放一个苹果，之后就不管这个盘子了，那么他是dp[i-1][j-1]，放了一个苹果所以i-1 ,丢了一个盘子j-1。
（三）
将n划分成不超过k的最大划分数
这个其实和第一个是一样的，状态转移方程也一样，这是返回值不一样而已，你仔细看看第一个对于dp数组的定义其实就是这个东西，不多说了好吧
（四）
将n划分成为几个奇正整数之和的划分数
我们设dp[i][j] 表示的是i这个数划分的最大值不超过k的时候的划分数，其实和第一个差不多就是这里有一个限制就是要是奇数
初始化：dp[][1] = 1 ;
转移方程：
当j为奇数的时候
dp[i][j] = dp[i-j][j] + dp[i][j-1];
dp[i][j] = dp[i][i];
当j为偶数的时候
dp[i][j] = dp[i][j-1]
解释一下转移方程，当他是奇数的时候，其实和第一个是一样的，但是只是奇数的时候才是一样的，当他是偶数的时候，我们知道j-1 是奇数，所以他是由dp[i][j-1] 转移过来的。
（五）
将n划分成几个不相同的正整数之和。
我们设dp[i][j]表示的是n这个数划分的最大值不超过k的划分数
初始化：
dp[][1] = 1; dp[1][] = 1,当他的最大划分为1的时候也就是说所有数都是1方案数是1，当他是1的时候，方案数也是1
转移方程 :
dp[i][j] = dp[i-j][j-1] + dp[i][j-1] (i>=j)
dp[i][j] = dp[i][i] （i<j）
解释一下转移方程，他说的是不能重复，所以当前数字是i，最大划分为j的时候，可以划分出一个j，又因为他不能重复，所以只能划分出一个j，划分完就不能用了，所以是dp[i-j][j-1]（划分完了），其他的都一样，他可以把j在划分一个1
总结完了上代码把（感觉自己的认知还是不深刻。。。要在看一下别人的博客呢）

#include <bits/stdc++.h>
using namespace std;
#define mes(a) memset(a,0,sizeof(a));
int n,k;
int a()//将n划分成若干正整数之和的划分数
{
	int dp[55][55];
	mes(dp);
	dp[0][0] = 1;
	for(int i = 0 ; i < 55;i++)
	{
		for(int j = 1 ; j < 55; j++)
		{
			if(i>=j)
			{
				dp[i][j] = dp[i-j][j] + dp[i][j-1];
			}
			else 
			{
				dp[i][j] = dp[i][i];
			}
		}
	}
	return dp[n][n];
}
int b()//将n划分成k个正整数之和的划分数。
{
	int dp[55][55];
	mes(dp);
	dp[1][1] =1;
	for(int i = 2 ; i <= 51 ; i++)
	{
		for(int j = 1 ; j <= i ; j++)
		{
			dp[i][j] = dp[i-1][j-1]+dp[i-j][j];
		}
	}
	return dp[n][k];
	
}
int c()//将n划分成若干正整数之和的划分数
{
	int dp[55][55];
	mes(dp);
	dp[0][0] = 1;
	for(int i = 0 ; i < 55 ; i++)
	{
		for(int j = 1 ; j < 55 ; j++)
		{
			if(i>=j)
			{
				dp[i][j] = dp[i-j][j] + dp[i][j-1];
			}
			else 
			{
				dp[i][j] = dp[i][i];
			}
		}
	}
	return dp[n][k];
}
int d()
{
	int dp[55][55];
	mes(dp);
	for(int i = 0 ; i <  55 ; i++)
	{
		dp[i][1] = 1;
		if(i&1)
		{
			dp[0][i] = 1;
		}
	}
	for(int i = 1 ; i < 55 ; i++)
	{
		for(int j = 1 ; j < 55 ; j++)
		{
			if(j&1)
			{
				if(i>=j)
				{
					dp[i][j] = dp[i-j][j] + dp[i][j-1];
				}
				else dp[i][j] = dp[i][i];
			}
			else 
			{
				dp[i][j] = dp[i][j-1];
			}
		}
	}
	return dp[n][n];
}
int e()
{
	int dp[55][55];
	mes(dp);
	dp[0][0] = 1;
	for(int i = 0 ; i < 55 ; i++)
	{
		for(int j = 1 ; j < 55 ; j++)
		{
			if(i>=j)
			{
				dp[i][j] = dp[i-j][j-1] + dp[i][j-1];
			}
			else 
			{
				dp[i][j] = dp[i][i];
			}
		}
	}
	return dp[n][n];
}
int main()
{
	while(cin>>n>>k)
	{
		printf("%d\n%d\n%d\n%d\n%d\n",a(),b(),c(),d(),e());
		puts("");
	}
}