[www.luogu.org] P1156 A trap of garbage *Solution*

Prob.2 of NOIP 2005 (Senior) Solution

酱油 posted @ Sun, 09 Aug 2015 20:20:05 +0800 in OI life with tags solution , 6774 readers

Aug. 9th, 2015. My birthday today.~

I finally got 100 pts. in the "difficult" DP problem (I've already told you in advance that I am always a WEAK DISH!).

"Sky Gate":http://www.luogu.org/problem/show?pid=1052

There is a long bridge whose length is L.
A frog wants to pass the bridge and starts jumping from Point 0(meters). (Note that he "conquerred" the bridge if his ending position is no less than L.)
He can only jump forward, and is able to move s(meter(s)) at least and t(meter(s)) at most.
There are m stones lying on the bridge and the frog hates to step on them. He can choose a method to make the number of stones he might step on as few as he can.
Then how many stones (at least) will the frog step on?
Input: 
L
s t m
a_1 a_2 ... a_m (indicating the positions of the stones)
Output:
S(indicating the smallest number of stones the frog would step on)
Sample Input:
10
2 3 5
2 3 5 6 7
Sample Output:
2
Explanations:
The frog starts from 0, and he jumps like this:
0 -> 2 -> 4 -> 6 -> 8 -> 10 (More solutions exist)

For 3 of 10 testcases: 1<=L<=10000;
For all 10 testcases: 1<=L<=1,000,000,000; 1<=s<=t<=10; 1<=m<=100; 0<=a_i<=L(1<=i<=m)

A typical DP problem in NOIP contests.

Suppose f[i] indicates the fewest number of stones that have been stepped on when the frog get to to position i, it is obvious that f[i]=max(f[i-t],f[i-t+1],...,f[i-s-1],f[i-s])+isstone[i]. isstone[i] shows whether there is a stone at current position i.

But it could only be able to get 30 pts., because it's time and room complexity can reach O(L×(t-s+1)), which is not able to solve the other 7 testcases.

We noticed that m is rather small compared with L, which meant the stones wouldn't be very densely placed. So we could consider "squeezing" the room. Then how can we do that?

It is EASY to find that the frog can easily get through a period without stones, whose length is len(>100). So we could do like this:

If two adjacent stones (stone_1 && stone_2) have a distance longer than 100, we could simply consider that their distance is 100, which wouldn't make sense to the answer.

Then L can be cut down to no more than 100×100=10000, which is acceptable to work out the problem easily!

    #include <cstdio>  
    #include <cstdlib>  
    #include <cstring>  
    #include <cmath>  
    #include <ctime>  
    #include <algorithm>  
    #include <iostream>  
    #define INF 2147483647  
    #define DONS 1000010  
    using namespace std;  
    int l,s,t,m,a[DONS],i,j,numst,stones[DONS],dp[DONS],minn;  
    bool ist[DONS];  
    int main()  
    {  
        scanf("%d%d%d%d",&l,&s,&t,&m);  
        for(i=1;i<=m;i++)scanf("%d",&a[i]);    
        if(s==t)  
        {  
            int ans=0;  
            for(i=1;i<=m;i++) ans+=!(a[i]%s);  
            printf("%d\n",ans);  
            return 0;  
        }  
        sort(a+1,a+m+1,less<int>());  
        for(i=1;i<=m;i++)  
        if(a[i]-a[i-1]<100) stones[i]=stones[i-1]+a[i]-a[i-1];else stones[i]=stones[i-1]+100;  
        for(i=1;i<=m;i++)ist[stones[i]]=1;  
        for(i=1;i<s;i++)dp[i]=INF;  
        dp[0]=0;  
        for(i=s;i<=stones[m]+t;i++)  
        {int US=INF;for(j=i-s;j>=max(i-t,0);j--)  
        US=min(US,dp[j]);dp[i]=US+ist[i];}  
        minn=INF;  
        for(i=stones[m];i<=stones[m]+t;i++)minn=min(dp[i],minn);  
        printf("%d\n",minn);  
        return 0;
    }

(In fact, DONS, the size of arrays can be cut down.)

My first time to write a DP program with room being cut down...

And I've learnt a lot through the experience.

If you have better solutions, please show your solution through comments, and I'll take it seriously.

(Comments are welcomed and it is recommended that you reply in English.)

Comments (66)

[Reply]

chrome clear cache said:
Sat, 29 Jun 2019 16:19:13 +0800

chrome clear cache this article also give you about windows 10 other post to using easily windows 10.

[Reply]

sport mental träning said:
Sun, 12 Jul 2020 22:12:44 +0800

Nice post. I was checking constantly this blog and I am impressed! Extremely helpful information specially the last part I care for such info a lot. I was seeking this particular information for a very long time. Thank you and good luck.
http://cse.google.com.gi/url?sa=i&url=https://merpessentials.com
<a href="http://cse.google.com.gh/url?sa=i&url=https://merpessentials.com">click here</a>

[Reply]

fake grass sheffield said:
Mon, 11 Jan 2021 21:20:19 +0800

If you set out to make me think today; mission accomplished! I really like your writing style and how you express your ideas. Thank you.

[Reply]

köksrenovering-stock said:
Wed, 13 Jan 2021 19:02:21 +0800

I would like to say that this blog really convinced me to do it! Thanks, very good post.

[Reply]

Business Listings said:
Thu, 21 Jan 2021 14:35:04 +0800

You have done a great job on this article. It’s very readable and highly intelligent. You have even managed to make it understandable and easy to read. You have some real writing talent. Thank you.

[Reply]

Business Listings said:
Mon, 25 Jan 2021 14:57:03 +0800

I am hoping the same best effort from you in the future as well. In fact your creative writing skills has inspired me.

[Reply]

American Biz Listing said:
Tue, 26 Jan 2021 20:16:25 +0800

Hello I am so delighted I located your blog, I really located you by mistake, while I was watching on google for something else, Anyways I am here now and could just like to say thank for a tremendous post and a all round entertaining website. Please do keep up the great work.

[Reply]

ABC Biz Listings said:
Fri, 29 Jan 2021 16:47:49 +0800

I am glad you take pride in what you write. This makes you stand way out from many other writers that push poorly written content.

[Reply]

iptv smarters said:
Sat, 30 Jan 2021 23:41:46 +0800

It is imperative that we read blog post very carefully. I am already done it and find that this post is really amazing.

[Reply]

smart iptv said:
Mon, 01 Feb 2021 00:24:10 +0800

Thanks for posting this info. I just want to let you know that I just check out your site and I find it very interesting and informative. I can't wait to read lots of your posts.

[Reply]

Kapp educational the said:
Mon, 01 Feb 2021 23:59:39 +0800

I like this post,And I guess that they having fun to read this post,they shall take a good site to make a information,thanks for sharing it to me.

[Reply]

SEO Services said:
Wed, 03 Feb 2021 01:31:05 +0800

Awesome article! I want people to know just how good this information is in your article. It’s interesting, compelling content. Your views are much like my own concerning this subject.

[Reply]

FIEX Marketing said:
Wed, 03 Feb 2021 22:48:31 +0800

This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work!.

[Reply]

Fire Watch Guards said:
Fri, 05 Feb 2021 15:18:53 +0800

Thank you for another great article. Where else could anyone get that kind of information in such a perfect way of writing? I have a presentation next week, and I am on the look for such information.

[Reply]

Reclaim Physical The said:
Sun, 07 Feb 2021 23:52:13 +0800

I really thank you for the valuable info on this great subject and look forward to more great posts. Thanks a lot for enjoying this beauty article with me. I am appreciating it very much! Looking forward to another great article. Good luck to the author! All the best!

[Reply]

Modesto concert said:
Mon, 08 Feb 2021 19:35:14 +0800

I am no expert, but I believe you just made an excellent point. You certainly fully understand what you are speaking about, and I can truly get behind that.

[Reply]

www.erbngreen.com said:
Wed, 17 Feb 2021 00:16:08 +0800

Positive site, where did u come up with the information on this posting? I'm pleased I discovered it though, ill be checking back soon to find out what additional posts you include.

[Reply]

www.erbngreen.com said:
Wed, 17 Feb 2021 00:16:25 +0800

Positive site, where did u come up with the information on this posting?I have read a few of the articles on your website now, and I really like your style. Thanks a million and please keep up the effective work.

[Reply]

Carl Scholz said:
Fri, 19 Feb 2021 15:17:01 +0800

Very good points you wrote here..Great stuff...I think you've made some truly interesting points.Keep up the good work.

[Reply]

corgis near me said:
Sat, 27 Feb 2021 20:40:25 +0800

Yes i am totally agreed with this article and i just want say that this article is very nice and very informative article.I will make sure to be reading your blog more. You made a good point but I can't help but wonder, what about the other side? !!!!!!THANKS!!!!!!

[Reply]

Tree Service Townsvi said:
Sun, 28 Feb 2021 19:58:01 +0800

Hi! Thanks for the great information you have provided! You have touched on crucuial points!

[Reply]

plumbers basingstoke said:
Mon, 01 Mar 2021 17:15:36 +0800

These are some great tools that i definitely use for SEO work. This is a great list to use in the future..

[Reply]

Chạy Ads Facebook gi said:
Fri, 05 Mar 2021 18:33:58 +0800

Very nice article, I enjoyed reading your post, very nice share, I want to twit this to my followers. Thanks!.

[Reply]

coffee machines said:
Fri, 05 Mar 2021 19:30:30 +0800

I have been checking out a few of your stories and i can state pretty good stuff. I will definitely bookmark your blog

[Reply]

photo femme site de said:
Sun, 07 Mar 2021 03:04:36 +0800

I have been checking out a few of your stories and i can state pretty good stuff. I will definitely bookmark your blog

[Reply]

KAI Asset Management said:
Mon, 15 Mar 2021 02:52:28 +0800

I wanted to thank you for this great read!! I definitely enjoying every little bit of it I have you bookmarked to check out new stuff you post.

[Reply]

bounce house rentals said:
Tue, 16 Mar 2021 18:42:21 +0800

Excellent website you have here, so much cool information!..

[Reply]

road bicycle rims said:
Wed, 17 Mar 2021 20:17:55 +0800

I have been checking out a few of your stories and i can state pretty good stuff. I will definitely bookmark your blog

[Reply]

click this site said:
Fri, 19 Mar 2021 15:42:10 +0800

Hi! Thanks for the great information you have provided! You have touched on crucuial points!

[Reply]

intercapefreightline said:
Sun, 21 Mar 2021 13:33:10 +0800

Thank you for helping people get the information they need. Great stuff as usual. Keep up the great work!!!

[Reply]

KC SanPedro said:
Mon, 22 Mar 2021 03:26:09 +0800

I just found this blog and have high hopes for it to continue. Keep up the great work, its hard to find good ones. I have added to my favorites. Thank You.

[Reply]

get more info said:
Wed, 31 Mar 2021 12:56:25 +0800

This is a great inspiring article.I am pretty much pleased with your good work.You put really very helpful information...

[Reply]

Showcase IDX said:
Wed, 31 Mar 2021 23:55:58 +0800

Thanks for your information, it was really very helpfull..

[Reply]

www.massparents.org said:
Mon, 05 Apr 2021 00:52:30 +0800

it was a wonderful chance to visit this kind of site and I am happy to know. thank you so much for giving us a chance to have this opportunity..

[Reply]

Tree Service Fort Wa said:
Wed, 07 Apr 2021 15:56:18 +0800

Its a great pleasure reading your post.Its full of information I am looking for and I love to post a comment that "The content of your post is awesome" Great work.

[Reply]

Tree Service Fort Wa said:
Wed, 07 Apr 2021 17:14:38 +0800

Wonderful blog! I found it while surfing around on Yahoo News. Do you have any suggestions on how to get listed in Yahoo News? I’ve been trying for a while but I never seem to get there! Appreciate it.

[Reply]

Red Robin Billings M said:
Thu, 08 Apr 2021 20:16:48 +0800

I just found this blog and have high hopes for it to continue. Keep up the great work, its hard to find good ones. I have added to my favorites. Thank You.

[Reply]

investing stock mark said:
Fri, 09 Apr 2021 16:37:09 +0800

[Reply]

private label lipsti said:
Fri, 09 Apr 2021 20:32:01 +0800

You have done a great job on this article. It’s very readable and highly intelligent. You have even managed to make it understandable and easy to read. You have some real writing talent. Thank you.

[Reply]

Private Label Lipsti said:
Sat, 10 Apr 2021 15:14:52 +0800

Please let me know if you’re looking for a article writer for your site. You have some really great posts and I feel I would be a good asset. If you ever want to take some of the load off, I’d absolutely love to write some material for your blog in exchange for a link back to mine. Please send me an email if interested. Thank you!

[Reply]

private label lipsti said:
Sat, 10 Apr 2021 15:17:47 +0800

Thanks for your post. I’ve been thinking about writing a very comparable post over the last couple of weeks, I’ll probably keep it short and sweet and link to this instead if thats cool. Thanks.

[Reply]

private label lipsti said:
Sat, 10 Apr 2021 15:27:28 +0800

If more people that write articles really concerned themselves with writing great content like you, more readers would be interested in their writings. Thank you for caring about your content.

[Reply]

www.staugustinecarpe said:
Sun, 11 Apr 2021 23:52:57 +0800

[Reply]

Vlone Shop said:
Mon, 12 Apr 2021 00:56:11 +0800

[Reply]

recommended reading said:
Tue, 13 Apr 2021 13:38:44 +0800

I am unable to read articles online very often, but I’m glad I did today. This is very well written and your points are well-expressed. Please, don’t ever stop writing.

[Reply]

famousworldpeople said:
Tue, 13 Apr 2021 15:11:48 +0800

Nice to read your article! I am looking forward to sharing your adventures and experiences.

[Reply]

Vlone Palm Angel t-s said:
Wed, 14 Apr 2021 23:47:59 +0800

Is it okay to post part of this on my website basically post a hyperlink to this webpage?

[Reply]

Photos of Pornstar said:
Tue, 06 Jul 2021 15:32:15 +0800

I was imagining getting such a post that is to an extraordinary degree supportive to us.

[Reply]

Escorts Dehradun said:
Sun, 10 Oct 2021 19:15:22 +0800

This is a great way to describe the blog in a great and effective way.

[Reply]

Bangalore Escorts said:
Wed, 03 Nov 2021 14:57:07 +0800

the first time I visit your website and I am very grateful to be here and read your amazing article.

[Reply]

twitter card validat said:
Wed, 10 Aug 2022 13:12:17 +0800

Twitter Card validator obviously used in Twitter and to know more about the validator. It is merely important to understand about the Twitter Card. In this article, we will come up with details of Twitter Card and Twitter Card validator and different type of cards available to make you understand better along with its usage. twitter card validator Twitter Card goes gives a link between your tweets by adding designed structured look and attracting more audience. In simple terms, the code must add to webpage and when someone shares your tweets link will display as Twitter Card.

[Reply]

HRMS - Wustl One - W said:
Sat, 20 Aug 2022 19:58:20 +0800

HRMS - Wustl One - Washington University in St. Louis. The Value of Time Tracking and Tips for Using HRMS Web Clock ... hrms wustl Notify your supervisor or HR at employeerelations @ wustl.edu if you believe you. View information on the transition to HRMS Web Clock. ... Learn about safety and security at the university and view Clery reports and logs at police.wustl.edu.

[Reply]

SUA NHA GIA RE said:
Sun, 23 Apr 2023 10:37:11 +0800

Thanks you!

Xây nhà trọn gói tại tphcm Thi cong alu Giá thi công nhà khung thép Sua nha gia re Giam sat cong trinh Xay nha gia re Wincons Wincons 8 Wincons 9 Wincons 10

[Reply]

https://winconsgroup said:
Sat, 02 Sep 2023 10:45:00 +0800

Thank Blog!

<a href ="https://winconsgroup.com/xay-nha-tron-goi-tai-tphcm/"> xây nhà trọn gói tại tphcm </a> <a href ="https://winconsgroup.com/thi-cong-alu/"> thi công alu </a> <a href ="https://winconsgroup.com/gia-thi-cong-nha-khung-thep/"> giá thi công nhà khung thép </a> <a href ="https://winconsgroup.com/sua-nha-gia-re/"> sửa nhà giá rẻ </a> <a href ="https://winconsgroup.com/giam-sat-cong-trinh/"> giám sát công trình </a> <a href ="https://winconsgroup.com/xay-nha-gia-re/"> xây nhà giá rẻ </a> <a href ="https://winconsgroup.com/"> Nhà thầu xây dựng </a> <a href ="https://winconsgroup.com/lan-can-cau-thang-sat/"> lan can cầu thang sắt </a> <a href ="https://winconsgroup.com/nha-tien-che-nho-dep/"> nhà tiền chế nhỏ đẹp </a> <a href ="https://winconsgroup.com/mai-che-dep/"> mai che dep </a> <a href ="https://winconsgroup.com/thi-cong-alu-gia-re/"> thi công alu giá rẻ </a> <a href ="https://winconsgroup.com/mau-cua-sat-dep/"> mẫu cửa sắt đẹp </a> <a href ="https://winconsgroup.com/cua-nhom-xingfa/"> cửa nhôm xingfa </a> <a href ="https://winconsgroup.com/nha-khung-sat/"> nhà khung sắt </a> <a href ="https://winconsgroup.com/nha-tien-che-2-tang/"> nhà tiền chế 2 tầng </a> <a href ="https://winconsgroup.com/sua-nha-tron-goi-tphcm/"> sửa nhà trọn gói tphcm </a> <a href ="https://winconsgroup.com/gia-cong-co-khi-theo-yeu-cau/"> gia công cơ khí theo yêu cầu </a> <a href ="https://winconsgroup.com/nha-thau-xay-dung-uy-tin-tphcm/"> nhà thầu xây dựng uy tín tphcm </a> <a href ="https://winconsgroup.com/thau-xay-nha-xuong/"> thầu xây nhà xưởng </a> <a href ="https://winconsgroup.com/mat-dung-alu/"> Mặt dựng alu </a> <a href ="https://winconsgroup.com/nha-lap-ghep/"> Nhà lắp ghép </a> <a href ="https://winconsgroup.com/nha-tien-che-2-2/"> Nhà tiền chế </a> <a href ="https://winconsgroup.com/tam-alu-gia-re/"> Tấm alu giá rẻ </a> <a href ="https://winconsgroup.com/mau-nha/"> Mẫu nhà </a>

[Reply]

https://winconsgroup said:
Sat, 02 Sep 2023 10:46:15 +0800 xây nhà trọn gói tại tphcm thi công alu giá thi công nhà khung thép sửa nhà giá rẻ giám sát công trình xây nhà giá rẻ Nhà thầu xây dựng lan can cầu thang sắt nhà tiền chế nhỏ đẹp Mái che đẹp thi công alu giá rẻ mẫu cửa sắt đẹp cửa nhôm xingfa nhà khung sắt nhà tiền chế 2 tầng sửa nhà trọn gói tphcm gia công cơ khí theo yêu cầu nhà thầu xây dựng uy tín tphcm thầu xây nhà xưởng Mặt dựng alu Nhà lắp ghép Nhà tiền chế Tấm alu giá rẻ Mẫu nhà

[Reply]

https://winconsgroup said:
Sat, 02 Sep 2023 10:46:58 +0800

Thanks Blog!

[Reply]

seo said:
Wed, 13 Nov 2024 03:24:34 +0800

Any way I'll be subscribing to your feed and I hope you post again soon. Big thanks for the useful info.I can see that you are an expert at your field! I am launching a website soon, and your information will be very useful for me.. Thanks for all your help and wishing you all the success in your business. Magazire

[Reply]

seo said:
Wed, 13 Nov 2024 03:27:24 +0800

I was surfing the Internet for information and came across your blog. I am impressed by the information you have on this blog. It shows how well you understand this subject.Very informative post! There is a lot of information here that can help any business get started with a successful social networking campaign. NewsMagzi

[Reply]

seo said:
Wed, 13 Nov 2024 03:31:09 +0800

Thanks for taking the time to discuss this, I feel strongly about it and love learning more on this topic. If possible, as you gain expertise, would you mind updating your blog with more information? It is extremely helpful for me.We are really grateful for your blog post. You will find a lot of approaches after visiting your post. I was exactly searching for. Thanks for such post and please keep it up. Great work.This is very nice one and gives indepth information. thanks for this nice article... News-Matrix

[Reply]

seo said:
Sun, 17 Nov 2024 21:16:35 +0800

Thanks for taking the time to discuss this, I feel strongly that love and read more on this topic. Wow, What a Excellent post. I really found this to much informatics. It is what i was searching for.I would like to suggest you that please keep sharing such type of info.ThanksYou make so many great points here that I read your article a couple of times. Your views are in accordance with my own for the most part. This is great content for your readers.You make so many great points here that I read your article a couple of times. Your views are in accordance with my own for the most part. This is great content for your readers. News Matic

[Reply]

seo said:
Sun, 17 Nov 2024 21:17:07 +0800

This is my first time visit here. From the tons of comments on your articles,I guess I am not only one having all the enjoyment right here!I havent any word to appreciate this post.....Really i am impressed from this post....the person who create this post it was a great human..thanks for shared this with us.I know your expertise on this. I must say we should have an online discussion on this. Writing only comments will close the discussion straight away! And will restrict the benefits from this information. TechyIntel

[Reply]

seo said:
Sun, 17 Nov 2024 21:17:30 +0800

Nice post! This is a very nice blog that I will definitively come back to more times this year! I just found this blog and have high hopes for it to continue. Keep up the great work, its hard to find good ones. I have added to my favorites. Thank You.I can set up my new idea from this post. It gives in depth information. Thanks for this valuable information for all,..This is just the information I am finding everywhere. This type of message always inspiring and I prefer to read quality content, so happy to find good place to many here in the post, the writing is just great, thanks for the post. VentsBulletin

[Reply]

seo said:
Mon, 18 Nov 2024 16:35:52 +0800

I really loved reading your blog. It was very well authored and easy to undertand. Unlike additional blogs I have read which are really not tht good. I also found your posts very interesting. In fact after reading, I had to go show it to my friend and he ejoyed it as well!Yes i am totally agreed with this article and i just want say that this article is very nice and very informative article.I will make sure to be reading your blog more. You made a good point but I can't help but wonder, what about the other side? !!!!!!Thanks Vital-Mag

[Reply]

seo said:
Mon, 18 Nov 2024 16:36:39 +0800

I’m going to read this. I’ll be sure to come back. thanks for sharing. and also This article gives the light in which we can observe the reality. this is very nice one and gives indepth information. thanks for this nice article...I would like to thank you for the efforts you have made in writing this article. I am hoping the same best work from you in the future as well. Thanks...I really loved reading your blog. It was very well authored and easy to undertand. Unlike additional blogs I have read which are really not tht good. I also found your posts very interesting. In fact after reading, I had to go show it to my friend and he ejoyed it as well! Silicon Insider

[Reply]

seo said:
Mon, 18 Nov 2024 16:37:22 +0800

Awesome article, it was exceptionally helpful! I simply began in this and I'm becoming more acquainted with it better! Cheers, keep doing awesome!This is such a great resource that you are providing and you give it away for free. I love seeing blog that understand the value. Im glad to have found this post as its such an interesting one! I am always on the lookout for quality posts and articles so i suppose im lucky to have found this! I hope you will be adding more in the future...Thanks for taking the time to discuss this, I feel strongly that love and read more on this topic. Usefullideas

[Reply]

seo said:
Mon, 18 Nov 2024 19:11:11 +0800

Superbly written article, if only all bloggers offered the same content as you, the internet would be a far better place..I know your expertise on this. I must say we should have an online discussion on this. Writing only comments will close the discussion straight away! And will restrict the benefits from this information.Superbly written article, if only all bloggers offered the same content as you, the internet would be a far better place..Very informative post! There is a lot of information here that can help any business get started with a successful social networking campaign.Awesome article, it was exceptionally helpful! I simply began in this and I'm becoming more acquainted with it better! Cheers, keep doing awesome! Technikerforscher

Soy Sauce's Blog

Prob.2 of NOIP 2005 (Senior) Solution

酱油

Categories

Bulletin

New Comments

New Messages

Links

RSS

Meta

Calendar

Counter

November
Sun	Mon	Tue	Wed	Thu	Fri	Sat
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30

Soy Sauce's Blog

Prob.2 of NOIP 2005 (Senior) *Solution*

酱油

Categories

Bulletin

New Comments

New Messages

Links

RSS

Meta

Calendar

Counter

Prob.2 of NOIP 2005 (Senior) Solution