#include<cstdio>
using namespace std;
int n,d,a[101];
bool dfs(int k){
if (k>d+1) return false;
if (a[k-1]>n||(a[k-1]<<(d-k+1))<n) return false;
if (a[k-1]==n) return true;
for (int i=k-1;i>0;i--)
for (int j=i;j>0;j--)
{
int x=a[i]+a[j];
if (x<=a[k-1]) break;
a[k]=x;if (dfs(k+1)) return true;
}
return false;
}
int main(){
scanf("%d",&n);a[1]=1;
for (d=2;;d++) if (dfs(2)) break;
printf("%d\n",d-1);
return 0;
}
扔完我自己也没看懂的标程走人。
另原题数据n<=2000打表可做。
using namespace std;
int n,d,a[101];
bool dfs(int k){
if (k>d+1) return false;
if (a[k-1]>n||(a[k-1]<<(d-k+1))<n) return false;
if (a[k-1]==n) return true;
for (int i=k-1;i>0;i--)
for (int j=i;j>0;j--)
{
int x=a[i]+a[j];
if (x<=a[k-1]) break;
a[k]=x;if (dfs(k+1)) return true;
}
return false;
}
int main(){
scanf("%d",&n);a[1]=1;
for (d=2;;d++) if (dfs(2)) break;
printf("%d\n",d-1);
return 0;
}
扔完我自己也没看懂的标程走人。
另原题数据n<=2000打表可做。
