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

酱油 posted @ Sun, 09 Aug 2015 20:20:05 +0800 in OI life with tags solution , 6678 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.)

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

Avatar_small
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>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Avatar_small
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

Avatar_small
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

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

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

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

Avatar_small
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

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

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

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

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

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

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

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

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

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

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

Avatar_small
investing stock mark said:
Fri, 09 Apr 2021 16:37:09 +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.

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

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

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

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

Avatar_small
www.staugustinecarpe said:
Sun, 11 Apr 2021 23:52:57 +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.

Avatar_small
Vlone Shop said:
Mon, 12 Apr 2021 00:56:11 +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!

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

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

Avatar_small
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?

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

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

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

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

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

Avatar_small
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>

 


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter