poj 2229 Sumsets dp

缘起

日常水题. poj 2229 Sumsets

分析

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
就是给你一个整数N, 求它的二进制分解方法种数. 例如N=7 有6种不同的分解方法
1) 1+1+1+1+1+1+1 
2) 1+1+1+1+1+2 
3) 1+1+1+2+2 
4) 1+1+1+4 
5) 1+2+2+2 
6) 1+2+4 

【输入】
N (1 <= N <= 100w)

【输出】
二进制分解种数模掉1e9的结果

【样例输入】
7

【样例输出】
6

【限制】
Time limit 2000 ms 
Memory limit 200000 kB

【来源】
USACO 2005 January Silver

dp. 区分n是奇数还是偶数. 对于奇数2n+1, 则所有分解中一定有1（例如7的所有分解种）

断言 f(2n+1)=f(2n). 因为对于每个2n的不同分解，加上1就可以映射到2n+1的一种分解，这是单射，所以f(2n+1)>=f(2n), 反过来, 对于2n+1的每种分解，都可以由f(2n)的一种分解+1得到. 所以f(2n+1)<=f(2n)

故而 f(2n+1)=f(2n).

而对于f(2n), 例如6的分解方式（果然是6种，和7一样）

1
2
3
4
5
6
1) 1+1+1+1+1+1 
2) 1+1+1+1+2 
3) 1+1+2+2 
4) 1+1+4 
5) 2+2+2 
6) 2+4

分成2种，一种是带1的，一种是不带1的，带1的去掉1就是 f(5), 不带1的除以2之后就是 f(3)（这些都可以使用上面一样的手段证明）

所以我们得到dp公式

1
2
dp(2n+1)=dp(2n)
dp(2n)=dp(2n-1)+dp(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
//#include "stdafx.h"

#include <stdio.h>
//#define LOCAL
typedef long long LL;
LL n, dp[1000005];
const LL BASE = 1e9;

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d", &n);
	dp[1] = 1, dp[2] = 2;
	for (int i = 3; i<=n; i++)
	{
		if (i&1)
		{
			dp[i] = dp[i-1];
		}
		else
		{
			dp[i] = (dp[i-1]+dp[i>>1])%BASE;
		}
	}
	printf("%lld\n", dp[n]%BASE);
	return 0;
}

ac情况

Status Accepted
Time 157ms
Memory 7912kB
Length 438
Lang C++
Submitted 2019-08-20 09:55:49
Shared
RemoteRunId 20771470

ps: 记忆化搜索会被T掉的. 下面的代码就被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
//#include "stdafx.h"

#include <stdio.h>
//#define LOCAL
typedef long long LL;
LL n, dp[1000005];
const LL BASE = 1e9;

LL sz(int i) // 记忆化搜索——降低dfs次数
{
	if (dp[i])
	{
		return dp[i]%BASE;
	}
	return (i&1)?sz(i-1):sz(i-1)+sz(i>>1);
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d", &n);
	dp[1] = 1, dp[2] = 2;
	printf("%lld\n", sz(n)%BASE);
	return 0;
}