c/ C - Sumsets

本文主要是介绍c/ C - Sumsets，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

用递归写的，然后超时了，知道应该去找规律，可是。。。。没找到尴尬

C - Sumsets

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

递归的码

#include <iostream>using namespace std;
int dou[25];
int num;
void findd(int n,int i)
{int  y=n/dou[i];if(dou[i]>n)return ;for(int j=y;j>=0;j--){ int  x=dou[i]*j;if(x+dou[i+1]==n||x==n){  num++;}elsefindd(n-x,i+1);}return;
}
int main()
{int n;for(int i=1,j=0;i<=1000000;i=i*2,j++)dou[j]=i;cin>>n;findd(n,0);cout<<num;return 0;
}

//然后大神找的规律


#include <iostream>
#include<cstring>
using namespace std;
int dou[25];
int num[25];
const int maxn=1000010;long long dp[maxn];
int main()
{int n;while(cin>>n){dp[0]=1;dp[1]=1;for(int i=2;i<=n;i++){if(i%2!=0)dp[i]=dp[i-1]%10000000000;//还不不懂这个100000000的意义所在elsedp[i]=(dp[i/2]+dp[i-1])%1000000000;}  cout << dp[n]<< endl;}return 0;
}

这篇关于c/ C - Sumsets的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---