hdu 1028 Ignatius and the Princess III 划分数

缘起

日常水题 hdu 1028 Ignatius and the Princess III

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
就是给你一个正整数N（1<=N<=120），求它的划分数.
例如N=4
4 = 4; 
4 = 3 + 1; 
4 = 2 + 2; 
4 = 2 + 1 + 1; 
4 = 1 + 1 + 1 + 1; 
所以4的划分数是5
注意，"4 = 3 + 1" 和 "4 = 1 + 3"是一样的.

【输入】
多样例，每行一个N

【输出】
对每个样例输出N的划分数

【限制】
Time limit 1000 ms
Memory limit 32768 kB

因为N较小，可以给出dfs（【1】中已经做过，但是没提交过）和dp两种做法.

dfs做法（但是我发现我天真了——被T掉了）

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
//#include "stdafx.h"

#include <stdio.h>
#define MIN(a,b) ((a)>(b)?(b):(a))
//#define LOCAL

int ans;

void sz(int n, int a) // 对n进行整数划分, a是划分的当前步骤中可以选择的最大数, 这里规定一种划分中数的排列一定是单调递减的(例如4=2+1+1, 2>=1>=1).
{
	if (!n) // 得到一种划分
	{
		ans++;
	}
	for (int i = a; i; i--)
	{
		sz(n-i, MIN(i,n-i)); // 下一步的最大值<=i,而且自然要<=n-i
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int n;
	while(~scanf("%d", &n))
	{
		ans = 0;
		sz(n, n);
		printf("%d\n", ans);
	}
	return 0;
}

下面是dp的ac做法

令

1
2
3
4
5
6
7
8
9
dp[i][j]为 i 按照题意划分为 不超过j个正整数的方法数. 则dp[n][n]就是我们要求的答案. 
则考虑i的每个j划分——如果这个划分中的正整数个数不足j的话（因为i的j划分定义是不超过j个正整数的和），则补0. 例
如 4 的 2划分为 4=1+3=2+2, 可以看做是 4+0, 1+3, 2+2 
则i的j划分就分成两类，一类是不含0的，例如上面的1+3和2+2, 另一类是含0的，例如上面的4, 对于不含0的, 都减去1，
例如 1+3 变成 0+2,2+2变成1+1，这就是2（=i-j）的全部划分. 对于（至少）含有（一个）0的, 看做i的j-1划分.
所以有
dp[i][j] = dp[i-j][j]+dp[i][j-1], 1<=j<=i<=n
初始值为
dp[i][1]=1, 1<=i<=n, dp[1][j] = 1, 1<=j<=n, dp[0][j] = 0 , 1<=j<=n, dp[i][0]=0, 1<=i<=n
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
//#include "stdafx.h"

#include <stdio.h>
//#define LOCAL

int dp[125][125]; // dp[i][j] 是i划分为不超过j个正整数的方法种数


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int n;
	while(~scanf("%d", &n))
	{
		for (int i = 1; i<=n;i++)
		{
			dp[i][1] = dp[1][i] = dp[0][i] = 1; // 注意,dp[i][1]和dp[1][i]都好说,都按照定义即可. dp[0][i]=1是因为你要知道为什么第一维会降到0? 是因为全部是1组成划分, 所以有1种划分,所以是1
		} // 初始化
		for (int i = 2; i<=n;i++)
		{
			for (int j = 2; j<=n; j++)
			{
				if (j<=i)
				{
					dp[i][j] = dp[i-j][j]+dp[i][j-1];
				}
				else // j>i的话, 则根据dp的定义,与dp[i][i]相等
				{
					dp[i][j] = dp[i][i];
				}
			}
		}
		printf("%d\n", dp[n][n]);
	}
	return 0;
}

ac情况

Status Accepted
Time 15ms
Memory 1796kB
Length 599
Lang C++
Submitted 2019-08-20 12:03:20
Shared
RemoteRunId 30359564

参考

【1】https://yfsyfs.github.io/2019/07/17/%E9%9D%A2%E8%AF%95%E9%A2%98-%E6%95%B4%E6%95%B0%E5%88%92%E5%88%86/