最新要闻

广告

手机

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

家电

Acw 170.加成序列

来源:博客园

题目描述

满足如下条件的序列 \(X\)(序列中元素被标号为 \(1、2、3…m\))被称为“加成序列”:

  1. \(X[1]=1\)
  2. \(X[m]=n\)
  3. \(X[1]
  4. 对于每个 \(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\),考虑爆搜,但是这个一般的爆搜过不去,原因如下:递归的层数可能很深(因为序列的长度可以很长),但是答案序列的长度会很短,举个例子,在这个序列中:

\[\large 1\ \ 2\ \ 3\ \ 5\ \ 8\ \ 13\ \ 21\ \ 34\ \ 55\ \ 89\ \ 144\]

\(\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 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

关键词: 估价函数 可能出现 无法达到