CF710E-Generate a String

2022-08-09 题解

题目大意：往串中插入或删除一个字符需要x秒钟，将串复制一遍需要y秒钟，问至少需要多少秒可以生成一个恰好含有n个字符的串。

注意一个性质：一个数肯定不可能由另一个数翻倍之后再连续加/减两次构成，因为这样不可能优于将原数加/减之后再翻倍。

#include <stdio.h>
#include <algorithm>
#define int long long
using namespace std;
int dp[10000005];
signed main()
{
    int n, x, y;
    scanf("%lld%lld%lld", &n, &x, &y);
    for (int i = 1; i <= n; i++)
    {
        dp[i] = dp[i - 1] + x;
        if (i % 2 == 0)
            dp[i] = min(dp[i], dp[i >> 1] + y);
        else
            dp[i] = min(dp[i], dp[i + 1 >> 1] + y + x);
    }
    printf("%lld", dp[n]);
    return 0;
}