【BZOJ】1677: [Usaco2005 Jan]Sumsets 求和(dp/规律)
http://www.lydsy.com/JudgeOnline/problem.php?id=1677
完全背包很容易想到,将1,2,4...等作为物品容量即可。
然后这题还有一个递推式
f[i]==f[i-1], 当i%2==1
f[i]==f[i-1]+f[i/2], 当i%2==0
当i为奇数时,我们可以看为i-1加上一个1的情况,那么只有f[i-1]中情况(因为每种情况只是多了一个1)
当i为偶数时,分为2种情况,含有1和不含有1,当含有1时,那么情况就是f[i-1],当不含有1时,情况就是f[i/2],因为不含有1他们都可以被2整除
背包:
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define for1(i,a,n) for(int i=(a);i<=(n);++i)
#define for2(i,a,n) for(int i=(a);i<(n);++i)
#define for3(i,a,n) for(int i=(a);i>=(n);--i)
#define for4(i,a,n) for(int i=(a);i>(n);--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define read(a) a=getint()
#define print(a) printf("%d", a)
#define dbg(x) cout << #x << " = " << x << endl
#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }
inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }
inline const int max(const int &a, const int &b) { return a>b?a:b; }
inline const int min(const int &a, const int &b) { return a<b?a:b; } const int N=1000005, MD=1000000000;
int f[N], n; int main() {
read(n);
f[0]=1;
for1(i, 0, 30) {
int s=1<<i;
if(s>n) break;
for(int j=s; j<=n; ++j)
{ f[j]+=f[j-s]; f[j]%=MD; }
}
print(f[n]);
return 0;
}
递推:
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define for1(i,a,n) for(int i=(a);i<=(n);++i)
#define for2(i,a,n) for(int i=(a);i<(n);++i)
#define for3(i,a,n) for(int i=(a);i>=(n);--i)
#define for4(i,a,n) for(int i=(a);i>(n);--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define read(a) a=getint()
#define print(a) printf("%d", a)
#define dbg(x) cout << #x << " = " << x << endl
#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }
inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }
inline const int max(const int &a, const int &b) { return a>b?a:b; }
inline const int min(const int &a, const int &b) { return a<b?a:b; } const int N=1000005;
int f[N], n; int main() {
read(n);
f[1]=1;
for1(i, 2, n) {
f[i]=f[i-1];
if(!(i&1)) f[i]+=f[i>>1];
f[i]%=1000000000;
}
print(f[n]);
return 0;
}
Description
Farmer John commanded his cows to search for different sets of numbers that sum to a given number. The cows use only numbers that are an integer power of 2. Here are the possible sets of numbers that sum to 7: 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 Help FJ count all possible representations for a given integer N (1 <= N <= 1,000,000).
给出一个N(1≤N≤10^6),使用一些2的若干次幂的数相加来求之.问有多少种方法
Input
一个整数N.
Output
方法数.这个数可能很大,请输出其在十进制下的最后9位.
Sample Input
Sample Output
有以下六种方式
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
HINT
Source
最新文章
- 篇一:MySQL中case when then
- Android工作学习第5天之Activity的完全退出程序
- 安卓下如何使用JUnit进行软件测试
- MVVM: 通过 Binding 或 x:Bind 结合 Command 实现,通过 ButtonBase 触发命令
- charles 常用设置
- dataTables表格分页排序等交互
- iOS,OC,图片相似度比较,图片指纹
- USB系列之六:基于DOSUSB的简单U盘驱动程序
- BZOJ 3626: [LNOI2014]LCA( 树链剖分 + 离线 )
- Visual Studio2017 远程调试 Remote Debugger
- bzoj 4501 旅行
- walle2.0 nginx.conf配置文件参数
- MySQL5.7.25(解压版)Windows下详细的安装过程
- C#网络请求与JSON解析
- 使用Semaphore控制对资源的多个副本的并发访问
- 求一个数组中重复数字的个数,要求复杂度为O(n)
- es6 中的 symbol
- Windows中几个内存相当的指标
- Python:Windows8下安装BeautifulSoup
- sse float 转int 截断和不截断