[CF 710E]Generate a String
转载请注明出处：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;
}
Jul 05, 2023 08:23:20 PM
Our team consists of professional writers and citizen journalists from tgpost.in who have diverse journalism interests and are dedicated to providing education tgpost.in updates in the public interest while remaining transparent. Our reporting team intends to provide the Education & Recruitment Update for all age groups and provide inside coverage to present a complete picture