Description
Input
Output
Sample Input
7
Sample Output
6
Source
这题是看一个数能用几个不同二次方幂的数和表示
首先来练习一下深搜把，这一开始我没想到还能用深搜，尽管不对，当然可慢啦啦啦啦
#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
int ans;
long long p[50];
void dfs(int n,int last)
{
if(n==0)
{
ans++;
return;
}
for(int i=0;n-p[i]>=0;i++)
{
if(p[i]>=last)
dfs(n-p[i],p[i]);
}
}
int main()
{
int n;
for(int i=0;i<=49;i++)
p[i]=pow(2,i);
cin>>n;
dfs(n,0);
printf("%d",ans);
return 0;
}
接下来是dp版的，不知道为啥，还是超时！！！！，但思想要学习下，看懂下面的那个dp更新表就欧克了
dp表假设只有1，然后添加2，然后添加4然后添加8，更新表
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
long long dp[1000001],p[30];
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
memset(dp,0,sizeof(dp));
p[0]=dp[0]=1;
for(int i=1;i<=29;i++)
{
p[i]=p[i-1]<<1;
}
for(int i=0;i<=29;i++)
{
if(p[i]<=n)
{
for(int j=p[i];j<=n;j++)
{
dp[j]=(dp[j]+dp[j-p[i]])%1000000000;
}
}
}
/*dp 1 2 3 4 5 6 7//假设输入7
1 1 1 1 1 1 1 1
2 2 2 3 3 4 4
4 4 4 6 6
*/
cout<<dp[n]<<endl;
}
}
最后过的是这个，我他喵。。。
#include<iostream>
#include<string.h>
using namespace std;
long long a[1000001];
int main()
{
int n;
a[1]=1,a[2]=2;
for(int i=3;i<1000001;i++)
{
a[i]=a[i-2]+a[i/2];
a[i]%=1000000000;
}
cin>>n;
cout<<a[n];
}
1.n为奇数，a[n]=a[n-1]
2.n为偶数：
（1）如果加数里含1，则一定至少有两个1，即对n-2的每一个加数式后面 +1+1，总类数为a[n-2]；
（2）如果加数里没有1，即对n/2的每一个加数式乘以2，总类数为a[n/2]；
原文：https://www.cnblogs.com/wpbing/p/9507853.html