poj 3181 Dollar Dayz 高精度+dp

缘起

学习完好听的银行家算法（当时我天真的以为该算法可以让我的资产快速翻倍~ QAQ）,又来日常水题了. poj 3181 Dollar Dayz 其实本题做过（【1】），只是在【1】的基础上加上了高精度——因为结果实在是太大了~

【1】的N范围仅仅在120以内——long long足以，而这里的N可达1000. 所以long long 无法支撑, 只能祭出高精度加法了.

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入n，和k，问将n用1到k这k个数字进行拆分，有多少种拆分方法。例如：
n=5,k=3 则有n=3+2,n=3+1+1,n=2+1+1+1,n=2+2+1,n=1+1+1+1+1这5种拆分方法

【输入】
N和K， 1 <= N <= 1000， 1 <= K <= 100

【输出】
不同方法数

【样例输入】
5 3

【样例输出】
5

【限制】
1s

dp+高精度，没什么好说的.dp的思路是

1
2
和【1】类似，令dp[i][j]是i用1,...,j进行划分的划分数. 则根据划分方案中有没有j，得到
dp[i][j] = dp[i][j-1]+dp[i-j][j]

于是不难写下如下代码

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

#include <stdio.h>
//#define LOCAL
typedef long long LL;
LL n,k, dp[1005][1005];

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%lld%lld", &n, &k))
	{
		for (int i = 1; i<=n;i++)
		{
			dp[i][0] = 0;
		}
		for (int i = 1; i<=k; i++)
		{
			dp[0][i] = 1;
		} // 初始化, 0进行划分只有一种方法——不选任何一个数
		for (LL j = 1; j<=k;j++)
		{
			for (LL i = 1; i<=n;i++)
			{
				if (i<j)
				{
					dp[i][j] = dp[i][i];
				}
				else
				{
					dp[i][j] = dp[i-j][j]+dp[i][j-1];
				}
			}
		}
		printf("%lld\n", dp[n][k]);
	}
	return 0;
}

但是WA了，因为LL 根本不够——n,k=(1000,1000)的时候答案可能到达32位数——远大于LL(LL 最多 9223372036854775807, 即19位数)， 所以基于原先写的高精度（【2】）的思想，我们用2个LL 来模拟本题的大数运算足够了——因为 18+18=36>32, 而不需要照搬【2】中的模板（试过，反而慢）

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

#include <stdio.h>
//#define LOCAL
typedef long long LL;
LL n,k, dp[1005][1005], dpp[1005][1005], BASE = 1e18; // dpp 是高18位, dp 是低18位

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%lld%lld", &n, &k))
	{
		for (int i = 1; i<=n;i++)
		{
			dp[i][0] = 0;
			dpp[i][0] = 0;
		}
		for (int i = 1; i<=k; i++)
		{
			dp[0][i] = 1;
			dpp[0][i] = 0;
		} // 初始化, 0进行划分只有一种方法——不选任何一个数
		for (LL j = 1; j<=k;j++)
		{
			for (LL i = 1; i<=n;i++)
			{
				if (i<j)
				{
					dp[i][j] = dp[i][i];
					dpp[i][j] = dpp[i][i];
				} // i<j的话 i用[1,j]划分和用[1,i]划分没有区别
				else
				{
					dp[i][j] = dp[i-j][j]+dp[i][j-1];
					dpp[i][j] = dpp[i-j][j]+dpp[i][j-1]+dp[i][j]/BASE; // 进位
					dp[i][j]%=BASE;
				}
			}
		}
		if (dpp[n][k])
		{
			printf("%lld", dpp[n][k]);
		}
		printf("%lld\n", dp[n][k]);
	}
	return 0;
}

ac情况

Status Accepted
Time 63ms
Memory 9704kB
Length 905
Lang C++
Submitted 2019-08-28 06:42:35
Shared
RemoteRunId 20810162

但是二这样就满足了么? 没有! 因为再次观察一下我们的dp公式

1
dp[i][j]=dp[i][j-1]+dp[i-j][j]

其实滚动一波就是（如果本题卡空间卡的比较紧的话，上述代码会MLE掉的）

1
dp[i]=dp[i]+dp[i-j]

而且因为i-j的j状态需要先被计算出来, 所以i和j的遍历都需要是正向的. 于是不难写下如下空间复杂度大幅优化的代码

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

#include <stdio.h>
//#define LOCAL
typedef long long LL;
LL n,k, dp[1005], dpp[1005], BASE = 1e18; // dpp 是高18位, dp 是低18位

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%lld%lld", &n, &k))
	{
		for (int i = 1; i<=n;i++)
		{
			dp[i] = 0;
			dpp[i] = 0;
		}
		dp[0] = 1;
		dpp[0] = 0;
		for (LL j = 1; j<=k;j++)
		{
			for (LL i = 1; i<=n;i++)
			{
				if (i<j)
				{
					dp[i] = dp[i];
					dpp[i] = dpp[i];
				} // i<j的话 i用[1,j]划分和用[1,i]划分没有区别
				else
				{
					dp[i] = dp[i-j]+dp[i];
					dpp[i] = dpp[i-j]+dpp[i]+dp[i]/BASE; // 进位
					dp[i]%=BASE;
				}
			}
		}
		if (dpp[n])
		{
			printf("%lld", dpp[n]);
		}
		printf("%lld\n", dp[n]);
	}
	return 0;
}

ac情况

Status Accepted
Time 63ms
Memory 100kB
Length 764
Lang C++
Submitted 2019-08-28 06:48:29
Shared
RemoteRunId 20810163

关注一下2份ac情况，后者只用了100KB，前者用了近9MB ! 可见算法优化的厉害~

参考

【1】https://yfsyfs.github.io/2019/08/20/hdu-1028-Ignatius-and-the-Princess-III-%E5%88%92%E5%88%86%E6%95%B0/

【2】https://yfsyfs.github.io/2019/08/07/hdu-1002-A-B-Problem-II-%E9%AB%98%E7%B2%BE%E5%BA%A6/