POJ 2248【加法链】

描述

　　对于一个数列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

输出样例1

解题思路

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

题解

 1 #include<bits/stdc++.h>
 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<ans)
24                 {
25                     ans=dep;
26                     return;
27                 }
28                 dfs(dep+1,num);
29             }
30         }
31     }
32 }
33 int main()
34 {
35     while(cin>>n)
36     {
37         memset(dp,0,sizeof(dp));
38         if(n==0)break;
39         ans=99999;
40         if(n<=2)
41         {
42             cout<<n<<endl;
43         }
44         else
45         {
46             dp[1]=1;
47             dp[2]=2;
48             dfs(3,2);
49             cout<<ans<<endl;
50         }
51         
52     } 
53     
54     
55 }