首页 > 其他 > 详细

cf 710E dp

时间:2016-10-11 21:43:59      阅读:126      评论:0      收藏:0      [点我收藏+]

题目链接: http://codeforces.com/problemset/problem/710/E

题意:要输入n个字符‘a‘,有两种操作,一种是输入或删除一个‘a‘,耗时x;另一种是把当前的整个文本复制粘贴,耗时y。求最少时间。

思路:dp 具体看代码=.=

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long

const int N=1e7+5;
ll dp[N];

ll minn(ll a,ll b){return a<b?a:b;}

int main()
{
    ll n,x,y;
    while(cin>>n>>x>>y)
    {
        dp[1]=x;
        for(int i=2; i<=n; i++)
        {
            if(i%2==0) dp[i]=minn(dp[i-1]+x,dp[i/2]+y);
            else dp[i]=minn(dp[i-1]+x,minn(dp[i/2]+x+y,dp[i/2+1]+x+y));
        }
        cout<<dp[n]<<endl;
    }
    return 0;
}

 

cf 710E dp

原文:http://www.cnblogs.com/a-clown/p/5950618.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!