<span>codeforces710E Generate a String（dp）</span>
题意：
给你一个n（1e7），和x，y
每次可以+1/-1/*2
+-花费x，*2花费y
问你从0变到n的最小花费
思路：
关键是n小啊~
对于每个i，他可能是由i-1加了1
或者i/2乘了2得来的
当前是奇数的时候，可能是i/2*2+1或者(i/2+1)*2-1得来的
前者在i-1加了1里包含了，所以只需要比较后者
/* *********************************************** Author :devil ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <stack> #include <map> #include <string> #include <cmath> #include <stdlib.h> #define LL long long #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=a;i>=b;i--) #define ou(a) printf("%d\n",a) #define pb push_back #define mkp make_pair template<class T>inline void rd(T &x) { char c=getchar(); x=0; while(!isdigit(c))c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } } #define IN freopen("in.txt","r",stdin); #define OUT freopen("out.txt","w",stdout); using namespace std; const int inf=0x3f3f3f3f; const int mod=1e9+7; const int N=1e7+10; LL dp[N],n,x,y; int main() { #ifndef ONLINE_JUDGE IN #endif rd(n),rd(x),rd(y); dp[1]=x; for(int i=2;i<=n;i++) { dp[i]=dp[i-1]+x; if(i&1) dp[i]=min(dp[i],dp[i/2+1]+x+y); else dp[i]=min(dp[i],dp[i>>1]+y); } printf("%I64d\n",dp[n]); return 0; }
