题目描述
满足如下条件的序列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
#include <bits/stdc++.h> using namespace std; const int N=110; int n,x[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 (x[i]+x[j]>last)//满足条件 { x[now+1]=x[i]+x[j]; int sm=dfs(now+1,deep,x[i]+x[j]);//下一步 if (sm) return sm; x[now+1]=0; } else//后面的肯定都不可能了,因为单调递增性不满足了. 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(x,0,sizeof(x)); x[1]=1; x[2]=2; s=dfs(2,k,2); if (s!=0) break; } } for(int i=1;i<=k;i++) cout<<x[i]<<" "; cout<<endl; } return 0; }或者在 dfs 内部对 sum 进行判重，这样可以进一步变快！
int dfs(int now,int deep,int last)//当前now深度,deep最大深度,last为上一次的数值,我们要满足数列的单调递增性. { bool sum[N]; memset(sum,0,sizeof sum); 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 (x[i]+x[j]>last)//满足条件 { if (x[i] + x[j] >= N || sum[x[i]+x[j]]) continue; sum[x[i]+x[j]] = true; x[now+1]=x[i]+x[j]; int sm=dfs(now+1,deep,x[i]+x[j]);//下一步 if (sm) return sm; x[now+1]=0; } else//后面的肯定都不可能了,因为单调递增性不满足了. break; } return 0; }非常感谢您！！！
强
顺便修改了一下blog的格式！！！
qaq
找茬，“记得初始化”没有被注释掉，害的我复制出去错了（狗头保命）
哇！
UVA529有加强版(n<=10000)，其实有用的剪枝就两个就够了: 1.在最优解中，每次搜索的下一个数一定可以由当前的最后一个数产生，因此枚举下一个数时一层循环就够了（性质的证明不大清楚） 2.使用迭代加深，利用已知深度的优势，由当前的最后一个数算出到最大深度时的数最大可能是多少，若<n就直接回溯
嗯呐.
棒棒哒的大佬
秦神！