首页 > 代码库 > cf 710 E Generate a String
cf 710 E Generate a String
题意：
开始你有数字$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 << 31) - 1);const double double_inf = 1e30;const double eps = 1e-14;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 0; int tem = (int)((double)rand() / RAND_MAX * x) % x; return o ? tem + 1 : tem;}ll ll_rand(ll x, int o) { if (!x) return 0; ll tem = (ll)((double)rand() / RAND_MAX * x) % x; return o ? tem + 1 : tem;}void data_gen() { srand(time(0)); freopen("in.txt", "w", stdout); int kases = 1; //printf("%d\n", kases); while (kases--) { ll sz = 100000; printf("%d\n", sz); FOR(i, 1, sz) { int o = Rand(2, 0); int O = Rand(26, 0); putchar(O + (o ? ‘a‘ : ‘A‘)); } putchar(‘\n‘); }}const int maxn = 1e7 + 10;ll n, x, y;ll dp[maxn];ll cal(ll num) { if (dp[num] != -1) return dp[num]; if (num == 1) return dp[num] = x; if (num & 1) return dp[num] = x + min(cal(num - 1), cal(num + 1)); if ((num >> 1) * x >= y) return dp[num] = y + cal(num >> 1); else return dp[num] = num * x;}int main() { //data_gen(); return 0; //C(); return 0; int debug = 0; if (debug) freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); while (~scanf("%lld%lld%lld", &n, &x, &y)) { clr(dp, -1); ll ans = cal(n); printf("%lld\n", ans); } return 0;}//382 81437847 324871127
cf 710 E Generate a String