题目描述
满足如下条件的序列 \(X\)（序列中元素被标号为 \(1、2、3…m\)）被称为“加成序列”：
- \(X[1]=1\)
- \(X[m]=n\)
- \(X[1]<X[2]<…<X[m-1]<X[m]\)
- 对于每个 \(k\)（\(2 \le k \le m\)）都存在两个整数 \(i\) 和 \(j\) （\(1 \le i,j\le k-1\)，\(i\) 和 \(j\) 可相等），使得 \(X[k]=X[i]+X[j]\)。
你的任务是：给定一个整数 \(n\)，找出符合上述条件的长度 \(m\) 最小的“加成序列”。
如果有多个满足要求的答案，只需要找出任意一个可行解。
解题思路
\(\qquad\) 看到 \(n\le 100\)，考虑爆搜，但是这个一般的爆搜过不去，原因如下：递归的层数可能很深（因为序列的长度可以很长），但是答案序列的长度会很短，举个例子，在这个序列中：
\(\qquad\)长度只有 \(11\)，但是很容易构造出一个递增的序列，可以达到 \(144\) 项。为了避免这样的不必要搜索，我们可以采用迭代加深搜索。
\(\qquad\qquad\qquad\)迭代加深搜索适合搜索规模不定，但是答案在较浅的层数的问题
\[\]\(\qquad\)具体就是我们先假定一个最大层数，在搜索的时候超过最大层数就不继续，知道搜索成功后，这个最大层数就是我们的答案。
剪枝操作
\(\qquad1.\)优化搜索顺序：因为这是严格递增顺序，所以为了让答案尽快趋近于 \(n\)，我们应该从后面的项开始，并且 \(a[i]\) 必定可以由 \(a[i - 1]\) 得到，这里可以采用反证法：因为如果 \(a[i]\) 的组成中不包含 \(a[i - 1]\)，那我们把 \(a[i - 1]\) 这一项删去不改变序列的性质，而且答案更优。所以 \(a[i]\) 必定可以由 \(a[i - 1]\) 得到，只要枚举另一个数就可以了。
\(\qquad2.\)排除等效冗余：由于两个数的和可能出现重复，所以我们要排除这种情况，搞个判重数组
\(\qquad3.\)估价函数：由于后一项至多是前一项的两倍，所以当当前数 \(a[i]\times 2^{m - i + 1} < n\) 的时候，代表无论如何也无法达到目标，所以也是不行的。
代码实现
#include <iostream>
using namespace std;
const int N = 110;
int n, path[N];
bool dfs(int u, int dep)
{
if (u == dep + 1) return path[dep] == n;
if (path[u - 1] * (1 << dep - u + 1) < n) return 0;
int st[N] = {0};
for (int j = u - 1; j >= 1; j -- )
{
int sum = path[u - 1] + path[j];
if (sum <= path[u - 1]) continue ;
if (st[sum] || sum > n) continue ;
path[u] = sum, st[sum] = 1;
if (dfs(u + 1, dep)) return 1;
}
return 0;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
path[1] = 1;
while (cin >> n, n)
{
int dep = 2;
while (!dfs(2, dep)) dep ++ ;
for (int i = 1; i <= dep; i ++ )
cout << path[i] << ' ';
cout << '\n';
}
return 0;
}
这些全部搞起来我们的代码就可以稳定 \(20ms\) 以内了 qwq
标签：le,int,qquad,dep,加成,Acw,序列,path,170 From： https://www.cnblogs.com/StkOvflow/p/17077286.html