题意：
开始你有数字$0$，你可以用代价$x$将该数字加$1$或减$1$（当$x > 0$时），或用代价$y$将该数字变为$2x$，那么问得到数字$n$所需的最少代价是多少。
数据范围$1 \leq x, y \leq 10^9$，$1 \leq n \leq 10^7$。
分析：
记得到数字$n$的代价为$f(n)$。
不加证明地给出如下结论：
注：可以通过观察数的二进制表达形式归纳证明下面的结论。
若$x = y$，则
$1^{\circ}$若$n$为偶数，则$f(n) = f(\frac{n}{2}) + y$ $(*)$
$2^{\circ}$若$n$为奇数，则$f(n) = min(f(n - 1), f(n + 1)) + x$ $(\#)$
把$(*)$当作主式，用$(\#)$式作为递推中间项，很容易计算出所有偶数位置对应的$f$值，从而计算出所有$f$值。
当$x, y$大小关系不确定时，我们只需修改偶数情况的更新规则。当$n$为偶数时，为了计算$f(n)$，需要归约到$f(1) = x$，在此过程中如果用到加倍操作，那么在当前位置
用效果必然最好（直观上如此，实际也可证明），否则就不用加倍操作。使用加倍操作后转移到$f(n / 2)$，代价为$y$，而不用加倍操作转移到$f(n / 2)$时代价为$x \cdot \frac{n}{2}$，使用加倍操作当且仅当$y <= x \cdot \frac{n}{2}$，因此将$(*)$更新为：
若$y <= x \cdot \frac{n}{2}$，$f(n) = f(\frac{n}{2}) + y$
否则$f(n) = n \cdot x$
可以用记忆话搜索来处理答案，空间复杂度$O(n)$，时间复杂度$O(log(n))$。
此外，还可以通过使用队列首先更新花费代价较小的位置来寻找答案，时间复杂度是$O(n)$，类似于$\text{bfs}$的过程。
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <ctime>
#include <functional>
#include <cmath>
#include <iostream>
#include <assert.h>
#pragma comment(linker, "/STACK:102400000,102400000")
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define mp std :: make_pair
#define st first
#define nd second
#define keyn (root->ch[1]->ch[0])
#define lson (u << 1)
#define rson (u << 1 | 1)
#define pii std :: pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define type(x) __typeof(x.begin())
#define foreach(i, j) for(type(j)i = j.begin(); i != j.end(); i++)
#define FOR(i, s, t) for(int i = (s); i <= (t); i++)
#define ROF(i, t, s) for(int i = (t); i >= (s); i--)
#define dbg(x) std::cout << x << std::endl
#define dbg2(x, y) std::cout << x << " " << y << std::endl
#define clr(x, i) memset(x, (i), sizeof(x))
#define maximize(x, y) x = max((x), (y))
#define minimize(x, y) x = min((x), (y))
using namespace std;
typedef long long ll;
const int int_inf = 0x3f3f3f3f;
const ll ll_inf = 0x3f3f3f3f3f3f3f3f;
const int INT_INF = (int)((1ll << ) - );
const double double_inf = 1e30;
const double eps = 1e-;
typedef unsigned long long ul;
typedef unsigned int ui;
inline int readint() {
int x;
scanf("%d", &x);
return x;
}
inline int readstr(char *s) {
scanf("%s", s);
return strlen(s);
} class cmpt {
public:
bool operator () (const int &x, const int &y) const {
return x > y;
}
}; int Rand(int x, int o) {
//if o set, return [1, x], else return [0, x - 1]
if (!x) return ;
int tem = (int)((double)rand() / RAND_MAX * x) % x;
return o ? tem + : tem;
}
ll ll_rand(ll x, int o) {
if (!x) return ;
ll tem = (ll)((double)rand() / RAND_MAX * x) % x;
return o ? tem + : tem;
} void data_gen() {
srand(time());
freopen("in.txt", "w", stdout);
int kases = ;
//printf("%d\n", kases);
while (kases--) {
ll sz = ;
printf("%d\n", sz);
FOR(i, , sz) {
int o = Rand(, );
int O = Rand(, );
putchar(O + (o ? 'a' : 'A'));
}
putchar('\n');
}
} const int maxn = 1e7 + ;
ll n, x, y;
ll dp[maxn]; ll cal(ll num) {
if (dp[num] != -) return dp[num];
if (num == ) return dp[num] = x;
if (num & ) return dp[num] = x + min(cal(num - ), cal(num + ));
if ((num >> ) * x >= y) return dp[num] = y + cal(num >> );
else return dp[num] = num * x;
} int main() {
//data_gen(); return 0;
//C(); return 0;
int debug = ;
if (debug) freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
while (~scanf("%lld%lld%lld", &n, &x, &y)) {
clr(dp, -);
ll ans = cal(n);
printf("%lld\n", ans);
}
return ;
} //382 81437847 324871127