AcWing 170. 迭代加深
原题链接
简单
作者:
想养一只皮卡丘
,
2020-11-14 23:59:30
,
所有人可见
,
阅读 657
#include <bits/stdc++.h>
using namespace std;
const int N=110;
int n,ans,x[N];
bool sum[N];
//当前now深度,deep最大深度,last为上一次的数值,因为要满足数列的单调递增性.
bool dfs(int now,int deep,int last){
if(x[now]==n) return 1; //递归边界
if(now>=deep) return 0; //深度限制(这里是大于等于,因为当now=k-1时,已经可以枚举出下一个,x数组中的数的个数刚好和k相等了)
for(int i=now;i>=1;i--) //从大到小枚举,快速逼近n
for(int j=i;j>=1;j--){
if(!sum[x[i]+x[j]]&&x[i]+x[j]>=last) //必须是大于等于last,因为可能出现两个数值一样的
{
x[now+1]=x[i]+x[j];
sum[x[i]+x[j]]=1;
//往下搜
bool banduan=dfs(now+1,deep,x[i]+x[j]);
if(banduan)
return 1;
//还原现场
sum[x[i]+x[j]]=0;
x[now+1]=0;
}
}
return 0;
}
int main()
{
while(cin>>n&&n)
{
//排除n=1,2的特殊情况
x[1]=1;
x[2]=2;
int k=n;
if(n>=3)
{
//k至少从3开始
k=3;
for(;k<=10;k++)
{
memset(sum,0,sizeof(sum));
memset(x,0,sizeof(x));
x[1]=1;x[2]=2; //前两个是唯一确定的
bool s=dfs(2,k,3);
//或者s=dfs(2,k,2)都可以
if(s)
break;
}
}
for(int i=1;i<=k;i++)
cout<<x[i]<<" ";
cout<<endl;
}
return 0;
}