题意

给你一个数字 $n$，设 $x$ 初始值为 $1$，问每次可以加上或减去一个前面出现过的 $x$，最少几次可以到达 $n$。$x$ 在操作中必须为正数。

思路

这个题目，我们可以想到在原来暴力的基础上进行优化，即使用 IDA*。

不会 IDA* 的可以看看我的博客。

现在想想怎么求出估价函数呢？如果从当前 $x$ 开始，不断加上最大的可以用的数字（也就是 $x$），那么相当于每次将 $x = x + x$，那么每次 $x$ 的值都可以变成 $2x$，那么假如现在还能操作 $cnt$ 次，如果 $x \cdot 2 ^ {cnt} < n$，那么在怎么样也到达不了目标，直接返回即可。

代码

/*******************************
| Author:  SunnyYuan
| Problem: Power Calculus
| Contest: Virtual Judge - POJ
| URL:     https://vjudge.net/problem/POJ-3134
| When:    2023-09-27 14:55:12
| 
| Memory:  64 MB
| Time:    5000 ms
*******************************/

#include <iostream>

using namespace std;

int n, depth, x;

int use[110], c;

bool dfs(int dep) {
    if (dep > depth) return false;
    if (x == n) return true;
    if (x << (depth - dep)<  n) return false;

    use[++c] = x;
    for (int i = 1; i <= c; i++) {
        int y = use[i];
        x += y;
        if (dfs(dep + 1)) return true;
        x -= y;
        if (x > y) {
            x -= y;
            if (dfs(dep + 1)) return true;
            x += y;
        }
    }
    c--;
    return false;
}

int main() {
    while (cin >> n, n) {
        x = 1;
        c = 0;
        for (depth = 0; ; depth++) {
            if (dfs(0)) {
                cout << depth << '\n';
                break;
            }
        }
    }
    return 0;
}