放牧代码和思想
专注自然语言处理、机器学习算法
    恕不接待索要源码语料者、索求技术方案者、以及不Google的懒人。

POJ 2229 Sumsets 题解 《挑战程序设计竞赛(第2版)》

2.3 记录结果再利用的“动态规划” 基础的动态规划算法

POJ 2229 Sumsets

将一个数N分解为2的幂之和共有几种分法?

定义dp[i]为i的分解方案数。dp[0] = 2 ^ 0 = 1,递推到 N 。若i为偶数,则dp[i] = dp[i / 2] + dp[i – 1] + 1,否则dp[i] = dp[i – 1] + 1。

#include <iostream>
using namespace std;

int dp[1000000 + 1]; // 数字i的分解数

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
	int N;
	cin >> N;
	dp[0] = 1; // 2^0
	for (int i = 1; i <= N; ++i)
	{
		if ((i & 0x1) == 0)
		{
			dp[i] = dp[ i / 2]; // 将i / 2的每个构成数乘以2,得到i
		}
		dp[i] += dp[i - 1]; // 将i - 1的构成数拿过来加一
		dp[i] %= 1000000000;
	}
	cout << dp[N] << endl;
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("out.txt");
#endif
    return 0;
}
///////////////////////////End Sub//////////////////////////////////

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » POJ 2229 Sumsets 题解 《挑战程序设计竞赛(第2版)》

分享到:更多 ()

评论 1

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    楼主,能给个证明么“定义dp [i] 为i的分解方案数。dp[0] = 2 ^ 0 = 1,递推到 N 。若i为偶数,则dp [i] = dp[i / 2] + dp[i – 1] + 1,否则dp [i] = dp[i – 1] + 1。”

    qingxi曾3年前 (2015-03-15)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机