题目描述
满足如下条件的序列X（序列中元素被标号为$1、2、3…m$）被称为“加成序列”：
1、$X[1]=1$
2、$X[m]=n$
3、$X[1]<X[2]<…<X[m-1]<X[m]$
4、对于每个 $k$（$2≤k≤m$）都存在两个整数 i 和 j （$1≤i,j≤k−1$，i 和 j 可相等），使得$X[k]=X[i]+X[j]$
你的任务是：给定一个整数n，找出符合上述条件的长度m最小的“加成序列”。
如果有多个满足要求的答案，只需要找出任意一个可行解。
输入格式
输入包含多组测试用例。
每组测试用例占据一行，包含一个整数n。
当输入为单行的0时，表示输入结束。
输出格式
对于每个测试用例，输出一个满足需求的整数序列，数字之间用空格隔开。
每个输出占一行。
数据范围
$1≤n≤100$
样例
输入样例：
5
7
12
15
77
0
输出样例：
1 2 4 5
1 2 4 6 7
1 2 4 8 12
1 2 4 5 10 15
1 2 4 8 9 17 34 68 77
玄学+剪枝+迭代加深搜索
这道题目,你首先可以明确地算出,最终m的长度必然是小于10的.
这就是迭代加深的精髓所在,就是我们确定答案在一个比较浅的位置.
玄学大杂烩:
我们可以推出在20以上的数,统统都是m>6的,而50以上的,除了64统统都是大于7的,这就是我们玄学数学优化,特别加速.
剪枝:下面是剪枝细目表
优化搜索顺序:我们要让序列中的数字迅速地逼近N,自然是要i和j从大到小枚举,且j<=i、
一定要注意这一点,不然你就会TLE,而且特别卡常.
排除等效冗余:我们发现,对于不同的i和j,他们的X[i]+X[j]有一定的可能性会相同
所以避免重复搜索,我们需要进行判重.
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N=110;
int n,x[N];
bool sum[N];
int dfs(int now,int deep,int last)//当前now深度,deep最大深度,last为上一次的数值,我们要满足数列的单调递增性.
{
if (x[now]==n)//找到了!!!
return now;
if (now>=deep)//如果已经超过深度了
return 0;
for(int i=now;i>=1;i--)
for(int j=i;j>=1;j--)//记得要j<=i 不然会TLE
if (!sum[x[i]+x[j]] && x[i]+x[j]>=last)//满足条件
{
x[now+1]=x[i]+x[j];
sum[x[i]+x[j]]=true;
int sm=dfs(now+1,deep,x[i]+x[j]);//下一步
if (sm)
return sm;
sum[x[i]+x[j]]=false;
x[now+1]=0;
} else if (!sum[x[i]+x[j]])//后面的肯定都不可能了,因为单调递增性不满足了.
break;
return 0;
}
int main()
{
while(cin>>n && n)
{
x[1]=1;
x[2]=2;
int s,k=n;
if (n>2)
{
if (n>20)//高端玄学优化
k=6;
else
k=3;
for(;k<=10;k++)
{
memset(sum,0,sizeof(sum));//记得初始化
memset(x,0,sizeof(x));
x[1]=1;
x[2]=2;
s=dfs(2,k,3);
if (s!=0)
break;
}
}
for(int i=1;i<=k;i++)
cout<<x[i]<<" ";
cout<<endl;
}
return 0;
}
“你首先可以明确地算出,最终m的长度必然是小于10的”这个怎么推的
1 2 4 8 16 32 64 128
yxc大佬上次讲了，明白了，谢谢你再讲一遍
大佬，你这里边的 sum 数组似乎没有起到作用，$x[i]+x[j]>=last$ 这个条件是强于!sum[x[i]+x[j]] 的，我对你的代码做了一下修改，耗时更少而且也能AC
或者在 dfs 内部对 sum 进行判重，这样可以进一步变快！
非常感谢您！！！
强
顺便修改了一下blog的格式！！！
qaq
找茬，“记得初始化”没有被注释掉，害的我复制出去错了（狗头保命）
哇！
$\text{UVA}529$有加强版$(n <= 10000)$，其实有用的剪枝就两个就够了: $1.$在最优解中，每次搜索的下一个数一定可以由当前的最后一个数产生，因此枚举下一个数时一层循环就够了（性质的证明不大清楚） $ 2.$使用迭代加深，利用已知深度的优势，由当前的最后一个数算出到最大深度时的数最大可能是多少，若$<n$就直接回溯
嗯呐.
棒棒哒的大佬
秦神！