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
8 1 1
Output
4
Input
8 1 10
Output
8 題目大意：
初始值為0，目标值為N，+1或者-1的操作對應花費為x，*2的操作對應花費為y、問最小花費。
思路：
1、考慮dp，設定dp【i】表示目标值為i的時候的最小花費。
那麼直接寫出其狀态轉移方程：
dp【i】=min（dp【i+1】，dp【i-1】）+x；
dp【i】=min（dp【i】，dp【i/2】）+y；
2、那麼我們發現，其中因為+1，-1的操作會使得dp過程中會存在環，而我們此時隻進行了一次狀态轉移，那麼顯然有情況會達不到最優、
接下來思路來自大牛：http://www.cnblogs.com/from00/p/5799795.html
①這個數如果是從i-1過來的，那麼一定有：dp【i】=min（dp【i-1】+y，dp【i】）；
②這個數如果是偶數，那麼一定有：dp【i】=min（dp【i/2】+y，dp【i】）；
③這個數如果是奇數，那麼一定有：dp【i】=min（dp【i/2+1】+y+x，dp【i】）；表示從（i/2+1）*2-1操作轉移過來。
Ac代碼：
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
#define ll __int64
ll dp[20000006];
int main()
{
int n;
ll x,y;
while(~scanf("%d%I64d%I64d",&n,&x,&y))
{
for(int i=1;i<=2*n;i++)dp[i]=2000000000000000000;
dp[1]=x;
for(int i=2;i<=2*n;i++)
{
dp[i]=min(dp[i],dp[i-1]+x);
if(i%2==0)
{
dp[i]=min(dp[i],dp[i/2]+y);
}
else dp[i]=min(dp[i],dp[i/2+1]+y+x);
}
printf("%I64d\n",dp[n]);
}
}