整数拆分
题目 整数拆分
思路分析
和上题基本一样 这次多了一个限制 不是由1-n-1的物品中选了 而是只在n的范围内的2^k中选
所以得先把物品处理出来
int cnt=1;
for(int i=1;i<=m;i*=2)
v[cnt++]=i;
n=cnt-1;
比如4 可以分为1111 112 22 4 在4的范围下只能有3个物品选
第1个物品为2^0=1 第2个物品为2^1=2 第3个物品为2^2=4
n表示物品总数 因为cnt是从1开始的 所以物品数量应该是cnt-1（第3个物品存进去后 cnt又++了一次）
物品处理出来了 n个物品 总价值不超过m 每个物品可多选 所以又是一个完全背包问题
（直接画优化后的图了 优化后其实就是一个反过来的01背包 所以也就是选与不选两种）
代码实现
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10,mod=1e9;
LL v[N],dp[N];
int n,m;
int main()
{
cin>>m;
int cnt=1;
for(int i=1;i<=m;i*=2)
v[cnt++]=i;
n=cnt-1;
dp[0]=1;
for(int i=1;i<=n;i++){
for(int j=v[i];j<=m;j++){
dp[j]=(dp[j]+dp[j-v[i]])%mod;
}
}
cout<<dp[m];
return 0;
}
💬 评论