题目描述

在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0,1,…,L0,1,…,L（其中LL是桥的长度）。坐标为00的点表示桥的起点，坐标为LL的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是SS到TT之间的任意正整数（包括S,TS,T）。当青蛙跳到或跳过坐标为LL的点时，就算青蛙已经跳出了独木桥。

题目给出独木桥的长度LL，青蛙跳跃的距离范围S,TS,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。

输入格式

第一行有11个正整数L(1 \le L \le 10^9)L(1≤L≤109)，表示独木桥的长度。

第二行有33个正整数S,T,MS,T,M，分别表示青蛙一次跳跃的最小距离，最大距离及桥上石子的个数，其中1 \le S \le T \le 101≤S≤T≤10,1 \le M \le 1001≤M≤100。

第三行有MM个不同的正整数分别表示这MM个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。

输出格式

一个整数，表示青蛙过河最少需要踩到的石子数。

输入输出样例

输入 #1<button class="copy&#45;btn lfe&#45;form&#45;sz&#45;middle" data&#45;v&#45;370e72e2="" data&#45;v&#45;52f2d52f="" type="button">复制</button> 
10
2 3 5
2 3 5 6 7
输出 #1<button class="copy&#45;btn lfe&#45;form&#45;sz&#45;middle" data&#45;v&#45;370e72e2="" data&#45;v&#45;52f2d52f="" type="button">复制</button> 
2

说明/提示

对于30%的数据，L \le 10000L≤10000；

对于全部的数据，L \le 10^9L≤109。

2005提高组第二题

 

思路

　　用 f [ i ] 来表示走到第 i 个格子踩的最小的石子数。

　　因为没办法开那么大的数组且 m 比较小，造成了太多不必要的计算浪费了时间，考虑去优化这个转移方程。

　　因为空地太多，而大空地中的跳跃实际上对答案并没有影响，所以考虑如何把路径压缩下来。

　　用到了一个叫小凯的疑惑的蓝题的一个结论，有兴趣的可以洛谷自行搜索下。

　　考虑这样一个问题，对于一个在 [ S , T ] 中的每个元素 x ， 只要 S != T  &&  X > S，都有一对元素 X - 1 和 X ，如果靠每次跳 X - 1 和 X 步来组合出跳的步数，最大可以跳 ( x - 2 ) * ( x - 1 ) - 1 的距离。

　　因为 T 最大为10， 可以令跳的最大步数为100，来把两两距离超过100的石头之间的路径压缩。

　　并且要特判一下 S == T 的情况， 这样的话只要求有多少石头在X的整数倍上就可以了。

 

CODE

 

#include  < bits/stdc++.h >
#define  dbg( x ) cout  <<  #x  <<  " = "  << x  << endl
#define  eps  1 e - 8
#define  pi  acos( - 1.0 )

using  namespace std ;
typedef  long  long LL ;

const  int inf  =  0x 3f3f3f3f ;

template < class T > inline  void  read(T  & res )
{
     char c ;T flag = 1 ;
     while((c = getchar()) < ' 0 ' ||c > ' 9 ' )if(c == ' - ' )flag =- 1 ;res =c - ' 0 ' ;
     while((c = getchar()) >= ' 0 ' &&c <= ' 9 ' )res =res * 10 +c - ' 0 ' ;res *=flag ;
}

namespace _buff  {
     const  size_t BUFF  =  1  <<  19 ;
     char  ibuf [BUFF ],  *ib  = ibuf ,  *ie  = ibuf ;
     char  getc()  {
         if  (ib  == ie )  {
            ib  = ibuf ;
            ie  = ibuf  +  fread(ibuf ,  1 , BUFF , stdin );
         }
         return ib  == ie  ?  - 1  :  *ib ++ ;
     }
}

int  qread()  {
     using  namespace _buff ;
     int ret  =  0 ;
     bool pos  =  true ;
     char c  =  getc();
     for  (;  (c  <  ' 0 '  || c  >  ' 9 ' )  && c  !=  ' - ' ; c  =  getc())  {
         assert( ~c );
     }
     if  (c  ==  ' - ' )  {
        pos  =  false ;
        c  =  getc();
     }
     for  (; c  >=  ' 0 '  && c  <=  ' 9 ' ; c  =  getc())  {
        ret  =  (ret  <<  3 )  +  (ret  <<  1 )  +  (c  ^  48 );
     }
     return pos  ? ret  :  -ret ;
}

const  int maxn  =  100007 ;

int l ;
int s , t , m ;

int  a [maxn ];
int  f [maxn ];
int  stone [maxn ];

int  main()
{
     read(l );
     read(s );read(t );read(m );
     for  (  int i  =  1 ; i  <= m ;  ++i  )  {
         read( a [i ]);
     }   
     if(s  == t )  {
         int ans  =  0 ;
         for  (  int i  =  1 ; i  <= m ;  ++i  )  {
             if( a [i ]  % s  ==  0 )  {
                 ++ans ;
             }
         }
        cout  << ans  << endl ;
         return  0 ;
     }
     sort(a  +  1 , a  + m  +  1 );
     for  (  int i  =  1 , last  =  0 , offset  =  0 ; i  <= m ;  ++i  )  {
         if( a [i ]  - last  >  100 )  {
            offset  +=  a [i ]  - last  -  100 ;
         }
        last  =  a [i ];
         a [i ]  -= offset ;
     }
    // for ( int i = 1; i <= m; ++i ) {
    //     dbg(a[i]);
    // }
     for  (  int i  =  1 ; i  <= m ;  ++i  )  {
         stone [ a [i ]]  =  1 ;
     }
    l  =  a [m ]  +  10 ;
    //f[0] = inf;
     for  (  int i  =  1 ; i  <= l ;  ++i  )  {
         f [i ]  =  200 ;
         for  (  int j  = s ; j  <= t ;  ++j  )  {
             if(i  - j  >=  0 )  {
                 f [i ]  =  min( f [i ],  f [i  - j ]  +  stone [i ]);
             }
         }
     }
    cout  <<  f [l ]  << endl ;
     return  0 ;
}