BZOJ 1677 [Usaco2005 Jan]Sumsets 求和:dp 无限背包 / 递推【2的幂次方之和】
2024-10-08 05:47:20
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1677
题意:
给定n(n <= 10^6),将n分解为2的幂次方之和,问你有多少种方法。
题解:
两种方法。
一、无限背包
将1,2,4,8...看作物品体积就好。
复杂度O(n*k),k约为20。
二、递推
对于dp[i],有两种情况。
(1)i为奇数。则分解结果中一定有1。
所以dp[i] = dp[i-1]。
(2)i为偶数。再分两种情况:
a. 分解结果中有1,所以dp[i] += dp[i-1]
b. 分解结果中没有1,即所有加数都是2的倍数。可以将所有加数都除以2,所以dp[i] += dp[i/2]
综上:dp[i] = dp[i-1] + dp[i/2]
AC Code(背包):
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 1000005
#define MOD 1000000000 using namespace std; int n;
int dp[MAX_N]; int main()
{
cin>>n;
memset(dp,,sizeof(dp));
dp[]=;
for(int i=;i<=;i++)
{
for(int j=(<<i);j<=n;j++)
{
dp[j]=(dp[j]+dp[j-(<<i)])%MOD;
}
}
cout<<dp[n]<<endl;
}
AC Code(递推):
// if is odd dp[i] = dp[i-1]
// if is even dp[i] = dp[i-1] + dp[i/2]
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 1000005
#define MOD 1000000000 using namespace std; int n;
int dp[MAX_N]; int main()
{
cin>>n;
memset(dp,,sizeof(dp));
dp[]=;
for(int i=;i<=n;i++)
{
if(i&) dp[i]=dp[i-];
else dp[i]=(dp[i-]+dp[i>>])%MOD;
}
cout<<dp[n]<<endl;
}
最新文章
- mysql 安装以及运行
- Autorun.inf文件(2):改变硬盘分区图标
- Debian 7 下安装CodeBlocks12.11
- 谈谈网站插入youtube视频播放
- hibernate(二)一级缓存和三种状态解析
- mongodb数据库实践笔记
- python自学笔记二
- bzoj2800
- etrace 跟踪 nginx之HTTP请求流程
- BZOJ 1029 [JSOI2007]建筑抢修 已更新
- Orchard学习
- 逆序一个8bit的2进制数
- bootstrap模态框远程加载网页的正确处理方式
- 进入子shell的各种情况分析
- 一步一步创建ASP.NET MVC5程序[Repository+Autofac+Automapper+SqlSugar](七)
- oracle第四天笔记
- openfire连接数据库mysql
- mapreduce的输入格式 --- InputFormat
- mysq在某一刻同时获取主从库的位置点
- Linux常用命令大全(转载)