題目描述 Description
在河上有一座獨木橋，一隻青蛙想沿着獨木橋從河的一側跳到另一側。在橋上有一些石子，青蛙很讨厭踩在這些石子上。由于橋的長度和青蛙一次跳過的距離都是正整數，我們可以把獨木橋上青蛙可能到達的點看成數軸上的一串整點：0，1，……，L（其中L是橋的長度）。坐标為0的點表示橋的起點，坐标為L的點表示橋的終點。青蛙從橋的起點開始，不停的向終點方向跳躍。一次跳躍的距離是S到T之間的任意正整數（包括S,T）。當青蛙跳到或跳過坐标為L的點時，就算青蛙已經跳出了獨木橋。
題目給出獨木橋的長度L，青蛙跳躍的距離範圍S,T，橋上石子的位置。你的任務是确定青蛙要想過河，最少需要踩到的石子數。
輸入描述 Input Description
輸入第一行有一個正整數L（1<=L<=109），表示獨木橋的長度。第二行有三個正整數S，T，M，分别表示青蛙一次跳躍的最小距離，最大距離，及橋上石子的個數，其中1<=S<=T<=10，1<=M<=100。第三行有M個不同的正整數分别表示這M個石子在數軸上的位置（資料保證橋的起點和終點處沒有石子）。所有相鄰的整數之間用一個空格隔開。
輸出描述 Output Description
輸出隻包括一個整數，表示青蛙過河最少需要踩到的石子數。
樣例輸入 Sample Input
10
2 35
2 3567
樣例輸出 Sample Output
2
資料範圍及提示 Data Size & Hint
資料規模
對于30%的資料，L<=10000；
對于全部的資料，L<=109。
題目思路
此題是一道典型的DP題，動規方程f[i]=min(f[i])+a[i](f[i]=到達i點所需最少石子數，a[i]=1表示i點有石子，a[i]=0表示i點無石子)，方程比較簡單，但考慮到此題資料範圍太大，單純使用這樣的普通DP必然逾時，而可能很長一段距離裡都沒有石子，那麼可以考慮使用狀态壓縮型DP，如下圖所示
第2、第3個點間距離超過了青蛙最大跳躍距離，則青蛙站在第2個石子上不可能跳到第3個石子去，第2、3個點間距離大于青蛙最大跳躍距離，而這個距離如果等于其最大跳躍距離(即一個臨界值)，青蛙一樣跳不過去，是以該距離可以壓縮為青蛙最大跳躍距離，如果兩個石子間的距離小于其最大跳躍距離，就不能壓縮（壓縮後距離反而變大了）
壓縮完成後，就可以将此題化為一般的DP題解決掉，然後AC
順便還要補充一下，最後的DP循環為什麼要循環到壓縮距離+最大跳躍距離，由題意可得青蛙不一定要落在終點，它可以落在終點後方，而青蛙站在終點（還是臨界值）跳時，最遠隻能落在壓縮距離+最大跳躍距離這個位置，是以要循環到這裡來，圖中“永遠不會溢出”打錯了。。。
下面是代碼
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define MAXN 100020
#define INF 100000000
using namespace std;
int min(int a,int b)
{
if(a<b)
return a;
return b;
}
int main()
{
int stone[200]; //stone[i]表示第i個石子距起點的長度
int pos[MAXN]={0};//pos[i]=1表示距起點距離為i的點有一個石子
int f[MAXN]; //f[i]=到距起點距離為i的點要經過的最少石子數
memset(f,0,sizeof(f));
memset(pos,0,sizeof(pos));
int distance=0,L,S,T,M,oldlen,ziplen,i,j; //distance=壓縮後每個石子的距離，oldlen=壓縮前的石子距離,ziplen=壓縮後的石子距離
scanf("%d%d%d%d",&L,&S,&T,&M);
for(i=1;i<=M;i++)
scanf("%d",&stone[i]);
sort(stone+1,stone+M+1); //将石子距起點長度升序排序
for(i=1;i<=M;i++) //循環，壓縮石子間的距離
{
oldlen=stone[i]-stone[i-1]; //壓縮前的石子間距
ziplen=T; //壓縮後的石子間距=青蛙單次跳躍最大距離
if(ziplen>oldlen) ziplen=oldlen; //如果壓縮距離大于原始距離，壓縮距離等于原始距離
distance+=ziplen; //更新壓縮後最後一個石子的位置
pos[distance]=1; //新的最後一個石子的位置标記為1，有石子
}
// f[0]=1;
for(i=1;i<=distance+T;i++)
//由于青蛙最後一次跳躍的落點位置可能大于壓縮後總距離distance,但它一定小于distance+T
//是以循環終點定為distance+T,i=目前青蛙的位置
{
int minn=INF; //到達i點經過的最少石子數
for(j=i-T;j<=i-S;j++) //要想到達i，j最近要到i-T,最遠到i-S
{
if(j>=0)
minn=min(minn,f[j]); //更新到達i點要經過的最少石子數(i點的石子不算)
}
f[i]=minn+pos[i];
}
int ans=INF;
for(i=distance;i<=distance+T;i++) //最終落點在區間[distance,distance+T]，尋找最優解的落點
ans=min(ans,f[i]);
if(S==T) //如果最小跳躍距離等于最大跳躍距離，那麼ans=距離是S(T)的倍數的石子數
{
ans=0;
for(i=1;i<=M;i++)
{
if(stone[i]%S==0) //第i個石頭的距離是S的倍數
ans++;
}
}
printf("%d\n",ans);
return 0;
}