【TopCoder SRM714】Salesman

相关链接

题目传送门: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;
		}
};

70 thoughts to “【TopCoder SRM714】Salesman”

  1. 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!

  2. 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!

  3. 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!

  4. 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!

  5. 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

  6. 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.

  7. 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!

  8. 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. . . . . .

  9. 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.

  10. 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.

  11. 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

  12. 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

  13. 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.

  14. 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

  15. 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

  16. 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!

  17. 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.

  18. 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!

  19. 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.

  20. 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.

  21. 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!

  22. 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

  23. 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?

  24. 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.

  25. 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!

  26. 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?

  27. 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.

  28. 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.

  29. 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.

  30. 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.

  31. 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..

  32. 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.

  33. 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!

  34. 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!

  35. 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

  36. 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

  37. 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

  38. 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.

  39. 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!

  40. 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?

  41. 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.

发表评论

电子邮件地址不会被公开。 必填项已用*标注