Vijos P1002 过河（NOIP提高组2005）

?

解析：

若 p*x+(p+1)*y=Q（采用跳跃距离p和p+1时可以跳至任何位置Q），则在Q ≥ P*（P-1）时是一定有解的。
由于题目给出的一个区间是1≤S≤T≤10，于是当相邻的两个石子之间的距离不小于8*9=72时，则后面的距离都可以到达，我们就可以认为它们之间的距离就是72。如此一来，我们就将原题L的范围缩小为了100*72=7200，动态规划算法完全可以承受了。

但是当S=T时，上述等式是无法使用的，在这种情况下，只需要在所有石子中，统计出坐标是S倍数的石子个数就可以了。

注意：

1.运用DP的时候，需要压缩

2.特殊解答S==T的时候

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; #define MIN(x,y) (x
        
         100) j += 100; else j += dis[i]-dis[i-1]; dd[j] = 1; } int k = j+100; dd[0] = 0; for(i=1; i<=k; ++i){ dp[i] = INF; for(j=S; j<=T; ++j){ if(i
         
          ?
          ?

Vijos P1002 过河 （NOIP提高组2005）