描述

 

 

　　对于一个数列a1,a2......am,其中a1 = 1,am = n , a1 < a2 < ... < am-1 < am 对于每个k(2<=k<=m),ak=ai+aj (1 <= i, j <= k-1),现给定n的值，要求m的最小值.

输入输出格式

输入

　　整个测试有多组数据，每行一个数字N，N<=100,测试以数字零代表结束。

输出

　　输出有多行，每行一个数字，代表你的结果

输入输出样例

输入样例1

571215770

输出样例1

45569

解题思路

　　咳咳，这道题和有点像（几乎一模一样）只需要注意换行（我当初没换爆了四次）再加一个while输入就行，所以，去看看吧，有思路的。

题解

1 #include
      
        2 using namespace std; 3 int n,ans=999999; 4 int dp[1001]; 5 void dfs(int dep,int pre) 6 { 7     int sum=-1; 8     int p=pre; 9     while(p<=n) 10     {11         p*=2;12         sum++;13     }14     if(dep+sum>=ans)return;15     for(int i=dep-1;i>=1;i--)16     {17         for(int j=i;j>=1;j--)18         {19             int num=dp[i]+dp[j];20             if(num>pre&&num<=n)21             {22                 dp[dep]=num;23                 if(num==n&&dep
       
        >n)36     {37         memset(dp,0,sizeof(dp));38         if(n==0)break;39         ans=99999;40         if(n<=2)41         {42             cout<
        
         <