Codeforces 710E Generate a String DP

題目連結：http://codeforces.com/problemset/problem/710/E

E. Generate a String time limit per test 2 seconds memory limit per test 512 megabytes input standard input output standard output

zscoder wants to generate an input file for some programming competition problem.

His input is a string consisting of n letters 'a'. He is too lazy to write a generator so he will manually generate the input in a text editor.

Initially, the text editor is empty. It takes him x seconds to insert or delete a letter 'a' from the text file and y seconds to copy the contents of the entire text file, and duplicate it.

zscoder wants to find the minimum amount of time needed for him to create the input file of exactly n letters 'a'. Help him to determine the amount of time needed to generate the input.

Input

The only line contains three integers n, x and y (1 ≤ n ≤ 107, 1 ≤ x, y ≤ 109) — the number of letters 'a' in the input file and the parameters from the problem statement.

Output

Print the only integer t — the minimum amount of time needed to generate the input file.

Examples Input Copy

8 1 1
      

Output

4
      

Input Copy

8 1 10
      

Output

8
      

題意：初始你在0位置，你想去n位置，你有2種操作方式，花費x，使目前位置+1或-1, 花費y使目前位置翻倍，問到達n的最小花費。

題解：分奇偶讨論，注意更新完dp[i]還要回過來更新dp[i-1].

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

#define x0 x0___
#define y0 y0___
#define pb push_back
#define SZ(X) ((int)X.size())
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define ALL(X) X.begin(),X.end()
#define RALL(X) X.rbegin(),X.rend()
#define rep(i,j,k) for(int i = j;i <= k;i ++)
#define per(i,j,k) for(int i = j;i >= k;i --)
#define mem(a,p) memset(a,p,sizeof(a))
#define fastio std::ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);


const ll MOD = 1E9 + 7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

ll qmod(ll a,ll b,ll c) {ll res=1;a%=c; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%c;a=a*a%c;}return res;}

template<typename T, typename S>
void upmax(T& a,S b){if(a<b) a=b;}
template<typename T, typename S>
void upmin(T& a,S b){if(a>b) a=b;}
template<typename T>
void W(T b){cout << b << endl;}
void gettle() {while(1);}
void getre() {int t=0;t/=t;}


/
/
/
/

const int N = 1E7 + 500;
ll dp[N];

int main()
{
    int n, x, y;
    scanf("%d %d %d", &n, &x, &y);
    mem(dp,0x3f);
    dp[1] = x;
    rep (i,2,n+1) {
        dp[i] = dp[i-1] + x;
        if(i & 1) {
            dp[i] = min( {dp[i], dp[i/2]+y+x, dp[i/2+1]+y+x });
        } else {
            dp[i] = min( {dp[i], dp[i/2] + y} );
        }
        if(2*i < N) dp[2*i] = min(dp[2*i], dp[i] + y);
        dp[i-1] = min(dp[i-1], dp[i] + x);
    }
    printf("%lld\n", dp[n]);
    return 0;
}