[CF 710E]Generate a String

danihao123 posted @ 2016年8月23日 11:25 in 题解 with tags 动态规划 codeforces , 322 阅读
转载请注明出处:http://danihao123.is-programmer.com/

很不错的题。

很容易想到大爆搜:每搜索一个点,预处理只插入的深度,然后限制之。之后再加一些其他的剪枝。不过估计会炸。

然后有同学就想:那个删除操作真特么棘手啊……因为这个就用不了DP了……哎

不过,删除的目的是什么?下一步干啥?再插入?那就有病了。肯定是要复制。所以说我们可以想出如下状态转移方程(i11r的TeX插件好像不能排版多行公式,所以分两部分写吧):

[tex]i[/tex]为偶数时[tex]f[i]=min(f[i-1]+x,f[i/2]+y)[/tex]

[tex]i[/tex]为奇数时[tex]f[i]=min(f[i-1]+x,f[(i+1)/2]+x+y)[/tex]

然后问题就迎刃而解了。

代码:

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1e7+2;
typedef long long ll;
#define REP(i,n) for(i=1;i<=(n);i++)
ll d[maxn];
int main(){
    ll n,x,y;
    cin>>n>>x>>y;
    register ll i;
    d[0]=0;
    REP(i,n+1)
        d[i]=x*i;
    REP(i,n){
        if(1&i){
            d[i]=min(d[i-1]+x,d[(i+1)/2]+x+y);
        }else{
            d[i]=min(d[i-1]+x,d[i>>1]+y);
        }
    }
    cout<<d[n]<<endl;
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter