题目传送门:http://codeforces.com/contest/710/problem/E
官方题解:http://codeforces.com/blog/entry/46761
这题,做法很多:
有简单粗暴型:http://www.cnblogs.com/Coolxxx/p/5797798.html
也有优雅递推型:http://blog.csdn.net/qq_33184171/article/details/52289905
我是第二种,不过第二种有一个东西需要证明:至少存在一组最优解使得-1操作至多连续进行1次
#include<bits/stdc++.h> #define LL long long #define abs(x) ((x)>0?(x):-(x)) using namespace std; const int N = 1e7+9; int n,x,y; LL f[N]; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar(); return ret*f; } int main(){ n = read(); x = read(); y = read(); f[1] = x; for (int i=2;i<=n;i++) { f[i] = f[i-1] + x; if (i & 1) f[i] = min(f[i], f[i+1>>1] + x + y); else f[i] = min(f[i], f[i>>1] + y); } printf("%I64d\n",f[n]); return 0; }
You need to take part in a contest for one of the highest quality
websites online. I’m going to recommend this website!
Hi to every one, the contents existing at this web site are
really remarkable for people knowledge, well, keep up the good
work fellows.
Hi there! Someone in my Facebook group shared this site with us so I came
to look it over. I’m definitely loving the information. I’m bookmarking and will be tweeting this to my followers!
Wonderful blog and wonderful design and style.
Hi, yup this article is really nice and I have learned lot of
things from it on the topic of blogging. thanks.
Stunning quest there. What occurred after?
Good luck!
Way cool! Some extremely valid points! I appreciate you penning this write-up and the rest of the website
is very good.
fantastic issues altogether, you just gained
a new reader. What might you recommend about your put up that you made some
days ago? Any positive?
Thanks for sharing your info. I truly appreciate your efforts and I am waiting
for your next write ups thank you once again.
My relatives every time say that I am killing my time here at net,
except I know I am getting know-how every day by reading thes pleasant
articles.
Hello I am so grateful I found your weblog, I really found you by error,
while I was looking on Askjeeve for something else, Anyways I am
here now and would just like to say thank you for a tremendous post and a all round thrilling blog (I also love the theme/design),
I don’t have time to go through it all at the moment but
I have saved it and also added your RSS feeds, so when I
have time I will be back to read more, Please do keep up the awesome work.
Hey! Do you know if they make any plugins to help with SEO?
I’m trying to get my blog to rank for some targeted keywords
but I’m not seeing very good results. If you know of any please share.
Appreciate it!
This piece of writing is in fact a fastidious one it assists new internet users, who are wishing in favor of blogging.
Good day! This is kind of off topic but
I need some advice from an established blog. Is it tough to set up your own blog?
I’m not very techincal but I can figure things out
pretty quick. I’m thinking about creating my own but I’m not sure where to start.
Do you have any ideas or suggestions? Many thanks
When some one searches for his required thing, so he/she needs to be available that in detail, so that
thing is maintained over here.
I blog often and I truly thank you for your information. The
article has truly peaked my interest. I am going to take a note of your site and keep checking for new details about once a week.
I opted in for your Feed too.
Wow! Finally I got a weblog from where I be able
to truly get valuable facts regarding my study and knowledge.
Thank you, I’ve recently been searching for information approximately this subject for a
while and yours is the best I have came upon till now.
However, what in regards to the conclusion? Are you sure about the
supply?
Quality articles or reviews is the crucial to interest the visitors to visit the
website, that’s what this site is providing.
Good day! I know this is kind of off topic but I was wondering which blog
platform are you using for this site? I’m getting sick and tired of WordPress
because I’ve had problems with hackers and I’m looking at options for another platform.
I would be awesome if you could point me in the direction of a good
platform.
Superb, what a web site it is! This weblog provides helpful
data to us, keep it up.
Excellent article. I will be going through some of these
issues as well..
Genuinely when someone doesn’t know then its up to other viewers that they will assist, so here it takes place.
Wow, that’s what I was seeking for, what a information! existing here at
this weblog, thanks admin of this site.
My partner and I stumbled over here coming from a different web page and thought I might check things out.
I like what I see so now i’m following you. Look forward to looking over your web page yet
again.
I like it whenever people come together and
share views. Great website, continue the good work!