首页 > 代码库 > cf 710E dp

cf 710E dp

题目链接: 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 longconst 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