qwq

我的博客qwq

题目

一个与$n$有关的整数加成序列$a_0,a_1,a_2,…,a_m$满足以下四个条件：

1.$a_0=1$

2.$a_m=n$

3.$a_0 < a_1 <a_2 <… <a_{m-1} <a_m$

4.对于每一个$k$($1≤k≤m$)都存在有两个整数$i$和$j$($0≤i$,$j≤k-1$,$i$和$j$可以相等)，使得$a_k=a_i+a_j$
你的任务是：给定一个整数n,找出符合上述四个条件的长度最小的整数加成序列。如果有多个满足要求的答案，只需要输出任意一个解即可。
举个例子，序列$<1,2,3,5>$和$<1,2,4,5>$均为$n=5$时的解。

poj2248

题解

蒟蒻的迭代加深入门题qwq
首先我看到这道题的时候不知道该怎么写，$dfs$？但是不知道序列中有几个数。$bfs$？但是状态该怎么记录。蒟蒻内心是崩溃的awsl
于是我就打了一个玄学暴搜，水过了30分qaq
下面开始$bb$正解
首先搜索一定要有明确的搜索框架，要明确自己要搜什么，不能漫无目的。对于这道题来说我们可以依次搜索序列中的每个位置$k$，枚举$i,j$，使得$x[k]=x[i]+x[j]$。
但是这样搜无疑效率很低，我们考虑剪枝：
1. 优化搜索顺序：为了让序列中的数字尽快接近$n$，我们可以从大到小来枚举$i,j$。
2. 排除等效冗余：对于不同的$i,j$，$x[i]+x[j]$可能是相等的，我们可以在枚举时开一个$bool$数组记录重复即可

敲黑板重点来了 对于本题来说，它的搜索分支非常的大，而最终状态却不会太大(序列长度$\leq10$)，于是我们可以限制搜索的深度，从1开始，如果大于当前的搜索深度立即退出，如果找到解则肯定是最优解退出即可。

这种限制搜索深度的方法就被称为迭代加深

code

#include <bits/stdc++.h> 
using namespace std; 
const int maxn = 110; 

template <class T> 
inline void read(T &s) {
   s = 0; 
   T w = 1, ch = getchar(); 
   while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
   while (isdigit(ch)) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
   s *= w;  
} 

int n, idt; 
int ans[maxn]; 

bool dfs(int k) {
   if (k > idt) {
    return ans[idt] == n ? true : false; 
   }
   bool vis[105]; 
   memset(vis, false, sizeof(vis)); 
   for (int i = k - 1; i >= 1; --i) {
    for (int j = i; j >= 1; --j) {
        if (ans[i] + ans[j] > n) continue; 
        if (vis[ans[i]+ans[j]]) continue; 
        if (ans[i] + ans[j] <= ans[k-1]) return false; 
        ans[k] = ans[i] + ans[j]; 
        vis[ans[k]] = true; 
        if (dfs(k + 1)) return true; 
    }
   }
   return false; 
}

int main() {
   ans[1] = 1; 
   ans[2] = 2; 
   while (1) {
    read(n); 
    if (!n) break; 
    if (n == 1) { puts("1"); continue; }
    for (idt = 1; ; ++idt) {
        if (dfs(2)) {
            for (int i = 1; i <= idt; ++i) 
                printf("%d ", ans[i]); 
            puts(""); 
            break; 
        }
    }
   }
   return 0; 
}