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

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