<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;
}

 

全部评论

相关推荐

醒工硬件:1学校那里把xxxxx学院去了,加了学院看着就不像本校 2简历实习和项目稍微精简一下。字太多,面试官看着累 3第一个实习格式和第二个实习不一样。建议换行 4项目描述太详细了,你快把原理图贴上来了。比如可以这样描述:使用yyyy芯片,使用xx拓扑,使用pwm控制频率与占空比,进行了了mos/电感/变压器选型,实现了xx功能 建议把技术栈和你做的较为有亮点的工作归纳出来 5熟悉正反激这个是真的吗
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务