记录编号	420473	评测结果	AAAAAAAAAA
题目名称	[NOIP 2005]过河	最终得分	100
用户昵称	Hyoi_iostream	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2017-07-04 21:03:19	内存使用	0.29 MiB

//过河    NOIP2005提高组复赛 DP+跳点   
#include <cstdio>  
#include <algorithm>  
#define inf 0x3f3f3f3f  
using namespace std;  
int f[15],now,M,S,T,L,stone[150];  
inline void input(){
    int i;  
    scanf("%d%d%d%d",&L,&S,&T,&M);  
    for(i=1;i<=M;i++)  
        scanf("%d",&stone[i]);  
    stone[++M]=L+T-1;  
    sort(stone+1,stone+M+1);  
}  
  
inline void change_into_min(){  
    int x=inf;  
    int i;  
    for(i=1;i<=T;i++)  
        x=min(x,f[i]);  
    for(i=0;i<=T;i++)  
        f[i]=x;  
}  
  
inline int fill(){  
    int i,mi,ma,j;  
    for(i=1;i<S;i++)f[i]=inf;  
    for(i=1;stone[i]<=T;i++)f[stone[i]]++;  
    ma=inf;  
    for(now=T+1;ma>100;now++){  
        ma=-inf;  
        for(j=1;j<=T;j++){  
            f[j-1]=f[j];  
            ma=max(ma,f[j]);  
        }  
        f[T]=inf;  
        for(j=S;j<=T;j++)  
            f[T]=min(f[T],f[T-j]);  
        if(now==stone[i] && now<=L)  
            f[T]++, i++;  
        ma=max(ma,f[T]);  
    }  
    return i;  
}  
  
inline int DP(){  
    int i,j,x;  
    for(i=fill();i<=M;i++)  
    {  
        if(stone[i]-now>2*T+S)  
        {  
            change_into_min();  
            now=stone[i];  
        }  
        for(;now<stone[i+1]&&now<=stone[i]+T;now++)  
        {  
            for(j=1;j<=T;j++)f[j-1]=f[j];  
            f[T]=inf;  
            for(j=S;j<=T;j++)f[T]=min(f[T],f[T-j]);  
            if(now==stone[i] && now<=L)f[T]++;  
        }  
    }  
    x=inf;  
    for(i=0;i<=T;i++)  
        x=min(x,f[i]);  
    return x;  
}  
  
inline int special(){  
    int i, cnt=0;  
    for(i=1;i<M;i++)  
        if(stone[i]%S==0)cnt++;  
    return cnt;  
}  
  
inline void work(){  //分类讨论 {  
    int ans;  
    if(S==T)ans=special();  
    else ans=DP();  
    printf("%d\n",ans);  
}  
  
int main(){
    freopen("river.in","r",stdin);
	freopen("river.out","w",stdout);  
    input();  
    work();  
    fclose(stdin);
    fclose(stdout);
    return 0;  
}