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

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


Login *


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