相关链接
题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=14120&rd=16883
神犇题解:http://codeforces.com/blog/entry/50602?#comment-358439
解题报告
设最终移动的范围为$[l,r]$
那么如果存在$r’ < r$且$sum_{l \to r’} \ge 0$,则$r’$优于$r$
所以我们可以枚举左端点,然后找到其对应的最优右端点
接下来就是区间内的路径规划问题
我们可以假设先走到左端点,那么剩下的东西的分配一定是尽量往左分配
这样就可以贪心了
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int INF = 1e9; const int N = 1e4; int pfx[N],delta[N],pos[N],nxt[N]; class Salesman { public: int minMoves(vector<int> ppos, vector<int> ddelta) { int n = ppos.size(); for (int i=1;i<=n;i++) { pos[i] = ppos[i - 1]; delta[i] = ddelta[i - 1]; } int ans = INF; ans = min(ans, solve(n)); for (int l=1,r=n;l<r;l++,r--) { swap(pos[l], pos[r]); swap(delta[l], delta[r]); } for (int i=1;i<=n;i++) { pos[i] = -pos[i]; } ans = min(ans, solve(n)); return ans; } private: inline int solve(int n) { int mn = INF, mx = -INF, ret = INF; for (int i=1;i<=n;i++) { pfx[i] = pfx[i-1] + delta[i]; if (delta[i] < 0) { mx = max(mx, i); mn = min(mn, i); } } for (int i=n,j=n;i;i--) { if (delta[i] < 0) { j = i; } nxt[i] = j; } if (mn == INF) { return 0; } for (int l=1;l<=mn;l++) { for (int r=mx;r<=n;r++) { if (pfx[r] - pfx[l - 1] >= 0) { ret = min(ret, cal(l, r)); break; } } } return ret; } inline int cal(int l, int r) { int ret = pos[r] - pos[l] + abs(pos[l]), ans = INF; int cry = 0, ned = 0, ptn = 0; for (int i=l;i<=r;i++) { if (delta[i] >= 0) { cry += delta[i]; if (cry >= ned && ned) { cry -= ned; ret += max(0, pos[i] - ptn) << 1; ned = 0; } } else if (delta[i] < 0) { if (!ned && cry >= -delta[i]) { cry += delta[i]; } else { if (!ned) { ptn = max(ptn, pos[i]); } ned -= delta[i]; } } ans = min(ans, ret + max(0, pos[r] - (ned? ptn: pos[nxt[i+1]]))); } return ans; } };
I every time spent my half an hour to read this web site’s articles daily along with
a mug of coffee.
Do you mind if I quote a couple of your articles as long as
I provide credit and sources back to your webpage?
My blog is in the very same niche as yours and my visitors would genuinely benefit from some of the information you present
here. Please let me know if this alright with you.
Thanks!
When I initially commented I clicked the “Notify me when new comments are added” checkbox and now each time
a comment is added I get four emails with the same comment.
Is there any way you can remove me from that service?
Thanks!
This is the right web site for everyone who really wants to understand this topic.
You realize so much its almost hard to argue with you (not
that I actually would want to…HaHa). You definitely put a
new spin on a topic that’s been written about for decades.
Excellent stuff, just great!
Thanks for the marvelous posting! I definitely enjoyed
reading it, you can be a great author. I will be sure to bookmark your blog and will come
back in the foreseeable future. I want to encourage yourself to continue your great work, have a nice afternoon!
Thanks for a marvelous posting! I definitely enjoyed reading it, you are a great author.
I will ensure that I bookmark your blog and will eventually come back very soon. I
want to encourage you to definitely continue your great work,
have a nice afternoon!
I just could not depart your site prior to suggesting that I really loved the
usual information an individual supply in your visitors?
Is gonna be again continuously in order to check out new posts
My family members always say that I am killing my time here at net,
however I know I am getting experience everyday by reading such fastidious articles.
My spouse and I absolutely love your blog and find many of
your post’s to be exactly what I’m looking for. Does one offer guest writers
to write content for yourself? I wouldn’t mind composing a post or
elaborating on many of the subjects you write regarding here.
Again, awesome blog!
This paragraph will help the internet users
for creating new blog or even a blog from start to end.
Hello very nice web site!! Guy .. Beautiful ..
Superb .. I’ll bookmark your web site and take the feeds additionally?
I’m happy to seek out so many helpful info right here within the submit, we
need develop more techniques on this regard, thank
you for sharing. . . . . .
Very nice write-up. I definitely appreciate this site. Keep writing!
Hi! Do you use Twitter? I’d like to follow you if that would be okay.
I’m undoubtedly enjoying your blog and look forward to new posts.
Fantastic goods from you, man. I’ve bear in mind your stuff previous to
and you are just extremely magnificent. I actually like what you have acquired right here, really like what you are saying and the way by which you assert it.
You make it entertaining and you continue to care for to stay it sensible.
I can’t wait to learn far more from you. This is really a terrific web site.
WOW just what I was looking for. Came here by searching for plenty of fish dating site
Way cool! Some very valid points! I appreciate you penning this write-up
plus the rest of the website is very good.
naturally like your web-site however you have to test the spelling on quite
a few of your posts. A number of them are rife with spelling
problems and I in finding it very bothersome to inform the reality nevertheless I
will surely come back again.
Valuable information. Lucky me I discovered your site by chance, and I’m
surprised why this accident didn’t happened in advance!
I bookmarked it. pof natalielise
This website was… how do I say it? Relevant!! Finally I have found
something that helped me. Thanks!
I don’t even know how I ended up here, but I thought this post was good.
I don’t know who you are but definitely you are going to a famous blogger if you are not already 😉 Cheers!
Hi there, I discovered your site by means of Google while searching for a related matter, your site came up, it appears good.
I’ve bookmarked it in my google bookmarks.
Hi there, simply was alert to your blog thru Google, and located that it is truly informative.
I am going to be careful for brussels. I’ll appreciate in case you proceed this in future.
A lot of folks will be benefited out of your writing.
Cheers! plenty of fish natalielise
Hello friends, how is everything, and what you would
like to say about this paragraph, in my view its genuinely remarkable in favor of me.
Heya just wanted to give you a quick heads up and let
you know a few of the pictures aren’t loading correctly.
I’m not sure why but I think its a linking issue. I’ve tried it in two different web browsers and both show the same outcome.
I know this if off topic but I’m looking into starting my own weblog and was curious
what all is needed to get set up? I’m assuming having
a blog like yours would cost a pretty penny? I’m
not very web savvy so I’m not 100% positive.
Any suggestions or advice would be greatly appreciated. Appreciate it pof natalielise
It’s the best time to make some plans for the future and it’s time to be happy.
I’ve read this post and if I could I want to suggest you few interesting things
or tips. Maybe you can write next articles referring to this article.
I desire to read more things about it! pof natalielise
It’s an remarkable paragraph for all the web visitors; they will take benefit from it I am sure.
It’s a shame you don’t have a donate button! I’d without a doubt donate to this brilliant blog!
I suppose for now i’ll settle for book-marking and adding your
RSS feed to my Google account. I look forward to new updates and will
talk about this site with my Facebook group. Talk soon!
Pretty! This has been an incredibly wonderful post.
Thanks for supplying this info.
With havin so much written content do you ever run into any
problems of plagorism or copyright violation? My site has a lot of exclusive
content I’ve either authored myself or outsourced but it appears a lot of it is popping
it up all over the web without my authorization. Do you know any ways to help stop content from being ripped off?
I’d truly appreciate it.
What’s up colleagues, how is all, and what you would like to
say concerning this post, in my view its actually awesome in support of
me.
I like the helpful info you provide in your articles.
I’ll bookmark your weblog and check again here frequently.
I’m quite certain I’ll learn many new stuff right here! Best
of luck for the next!
Quality articles is the crucial to attract the people to visit the web site,
that’s what this site is providing.
Saved as a favorite, I love your web site!
Hi there I am so grateful I found your website, I really
found you by error, while I was browsing on Google for something else, Anyways
I am here now and would just like to say thanks for a fantastic post and a all round enjoyable blog (I also love the theme/design),
I don’t have time to go through it all at the
minute but I have book-marked it and also included your RSS feeds, so when I have time I will be back
to read a lot more, Please do keep up the fantastic job.
I do believe all the ideas you’ve offered to your post.
They are really convincing and can definitely
work. Nonetheless, the posts are too quick for novices.
May you please prolong them a bit from subsequent time?
Thank you for the post.
Hi, yup this article is in fact good and I have learned lot of things
from it regarding blogging. thanks.
This is very interesting, You are a very skilled blogger.
I have joined your rss feed and look forward to
seeking more of your excellent post. Also, I’ve shared your
web site in my social networks!
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 setting up my own but I’m not sure where to start.
Do you have any points or suggestions? Appreciate it
What’s up, everything is going well here and ofcourse every
one is sharing facts, that’s actually good, keep up writing.
I am really enjoying the theme/design of your weblog.
Do you ever run into any internet browser compatibility problems?
A small number of my blog audience have complained about my website not operating correctly in Explorer but
looks great in Safari. Do you have any solutions to help fix this problem?
As the admin of this web site is working, no
hesitation very quickly it will be renowned, due to its quality contents.
Hi to every one, for the reason that I am really eager of reading this website’s post to
be updated on a regular basis. It carries fastidious stuff.
I do believe all the concepts you have offered on your post.
They are very convincing and will certainly work. Nonetheless, the posts
are very brief for newbies. May you please lengthen them
a little from subsequent time? Thanks for the post.
Hi everyone, it’s my first pay a quick visit at this site, and paragraph is in fact fruitful designed for
me, keep up posting such articles or reviews.
Awesome blog! Do you have any hints for aspiring writers?
I’m hoping to start my own site soon but I’m
a little lost on everything. Would you suggest starting with a free platform like
Wordpress or go for a paid option? There are so many options out there that I’m totally overwhelmed ..
Any suggestions? Bless you!
I was curious if you ever thought of changing the page layout of your
blog? Its very well written; I love what youve got
to say. But maybe you could a little more in the way of
content so people could connect with it better. Youve got an awful lot of text for only having
1 or 2 pictures. Maybe you could space it out better?
Have you ever thought about publishing an ebook or guest
authoring on other websites? I have a blog based upon on the same subjects you
discuss and would really like to have you share some stories/information. I know my visitors would enjoy your work.
If you’re even remotely interested, feel free to send me an email.
Its like you read my mind! You seem to know a lot about this, like you wrote the book in it
or something. I think that you could do with some pics to
drive the message home a little bit, but instead of that, this is excellent
blog. A fantastic read. I will definitely be back.
That is a good tip particularly to those fresh to the blogosphere.
Simple but very precise information… Many thanks for
sharing this one. A must read article!
Hey there! Someone in my Facebook group shared this site with us so I came to look it over.
I’m definitely enjoying the information. I’m book-marking and will
be tweeting this to my followers! Excellent blog and terrific design.
Simply want to say your article is as astonishing. The clarity in your publish is simply excellent and i
could assume you are knowledgeable on this subject.
Well with your permission let me to grasp your feed
to stay updated with imminent post. Thanks 1,000,000 and
please keep up the enjoyable work.
I am extremely impressed along with your writing skills and
also with the structure for your blog. Is that this a paid subject
or did you modify it your self? Anyway stay up the excellent quality writing,
it’s uncommon to look a great weblog like this one these days..
Hey I know this is off topic but I was wondering if you knew of
any widgets I could add to my blog that automatically tweet
my newest twitter updates. I’ve been looking for a plug-in like this
for quite some time and was hoping maybe you would have some experience with something like this.
Please let me know if you run into anything. I truly enjoy reading your blog and I look forward to your
new updates.
Hi, I read your blogs regularly. Your writing
style is awesome, keep it up!
Why visitors still use to read news papers when in this technological world all is accessible
on web?
It is appropriate time to make some plans for the future and
it is time to be happy. I have read this post and if I could
I wish to suggest you few interesting things or suggestions.
Maybe you could write next articles referring to this article.
I want to read more things about it!
Hi there, I discovered your site by means of Google while
looking for a comparable topic, your web site got here
up, it appears to be like good. I’ve bookmarked it in my google bookmarks.
Hello there, simply became alert to your blog
via Google, and located that it’s really informative.
I am gonna be careful for brussels. I’ll be grateful if
you continue this in future. Numerous folks shall be
benefited from your writing. Cheers!
My family members every time say that I am
killing my time here at net, but I know I am getting knowledge daily by reading
such nice articles.
I really like your blog.. very nice colors & theme. Did you create this website yourself or
did you hire someone to do it for you? Plz answer back as I’m looking to design my own blog and would like to find out where u got this from.
thanks a lot
I pay a quick visit daily a few sites and sites to read articles, however this weblog gives
feature based writing.
Thank you a lot for sharing this with all folks you actually realize
what you are talking approximately! Bookmarked. Kindly additionally talk over with my web site =).
We can have a hyperlink change contract among us
This site was… how do I say it? Relevant!! Finally I have
found something which helped me. Kudos!
Excellent beat ! I wish to apprentice at the same time as you amend your website, how could i subscribe for
a weblog web site? The account helped me a acceptable deal.
I were tiny bit familiar of this your broadcast provided shiny transparent idea
I do not even understand how I stopped up right
here, however I assumed this publish was good. I don’t understand who you’re however certainly you are going to a famous blogger for those who are
not already. Cheers!
Its like you read my mind! You appear to know so much about
this, like you wrote the book in it or something.
I think that you can do with a few pics to drive the message home a little bit,
but other than that, this is wonderful blog. A great read.
I’ll certainly be back.
Hey there would you mind letting me know which web host you’re working with?
I’ve loaded your blog in 3 different web browsers and I must say this blog loads a lot quicker then most.
Can you recommend a good internet hosting provider at a
honest price? Thanks a lot, I appreciate it!
It’s very straightforward to find out any matter on net as
compared to textbooks, as I found this article at this website.
I think the admin of this website is really working hard in favor of his web
page, as here every material is quality
based information.
I know this web site presents quality dependent articles or reviews and extra information,
is there any other web site which offers these kinds of stuff in quality?
Hello all, here every person is sharing these kinds of know-how,
thus it’s fastidious to read this weblog, and I used to visit this web site every
day.
Hey would you mind letting me know which hosting company you’re working with? I’ve loaded your blog in 3 different browsers and I must say this blog loads a lot faster then most. Can you suggest a good web hosting provider at a honest price? Thank you, I appreciate it!
We’re a bunch of volunteers and opening a brand new scheme in our community.
Your website provided us with valuable information to work on. You have done an impressive activity and our
whole neighborhood will be thankful to you.
Attractive section of content. I just stumbled upon your
weblog and in accession capital to assert that I acquire actually enjoyed account your blog posts.
Anyway I’ll be subscribing to your augment and even I achievement you access
consistently quickly.
of course like your web-site however you have to test the spelling on several of your posts.
A number of them are rife with spelling issues and I in finding it very bothersome
to tell the truth then again I will definitely come again again.
You’re so awesome! I do not think I’ve truly read a single thing like this before.
So great to discover somebody with some original thoughts on this subject matter.
Really.. thanks for starting this up. This web site is one thing that is required on the web,
someone with some originality!
Tremendous things here. I’m very happy to peer your article.
Thank you so much and I’m having a look ahead to contact you.
Will you please drop me a mail?
I am extremely inspired with your writing abilities and also with the
layout for your weblog. Is that this a paid subject matter or did you customize it yourself?
Either way keep up the nice quality writing, it is uncommon to peer
a great weblog like this one today..
Hello would you mind letting me know which hosting company you’re utilizing?
I’ve loaded your blog in 3 different internet browsers and
I must say this blog loads a lot faster then most. Can you suggest a good web hosting provider at a honest
price? Thank you, I appreciate it!
Greetings! Very useful advice in this particular post!
It’s the little changes which will make the greatest changes.
Thanks a lot for sharing!
It’s great that you are getting thoughts from this post as well as from our discussion made here.
We absolutely love your blog and find almost all of your
post’s to be exactly what I’m looking for. Does
one offer guest writers to write content in your case? I wouldn’t mind publishing a post or elaborating on a few
of the subjects you write about here. Again, awesome website!
Thanks for the good writeup. It actually was once a enjoyment account it.
Glance complicated to far introduced agreeable from you! However,
how could we keep up a correspondence?
It’s really a nice and helpful piece of info. I’m satisfied that
you shared this useful info with us. Please keep us
informed like this. Thanks for sharing.
I really treasure your work, Great post.
Its like you read my mind! You seem to know so
much about this, like you wrote the book in it or something.
I think that you could do with a few pics to drive the message home a little
bit, but instead of that, this is fantastic blog.
An excellent read. I’ll definitely be back.
Muchos Gracias for your blog article.Much thanks again. Want more.
I truly appreciate this article.Thanks Again. Want more.