这道题要用到压缩的思想（原来DP还能这么用。。。）
其实很简单，假如我们要到某一个位置w
如果我们原位置为Q
很显然，如果（W-Q>=s*t）那么我们一定能到达W
换言之，就是如果我们我们可以到达s*t+1~s*t+t的任意位置
然后我们就可以取膜啦
每次最多只能前进100格，100次后只能前进10000格
那么就可以DP啦，是不是很神奇？
但是我们要考虑一种特殊情况，如果s=t，那么上述方法是没有任何效果的。
所以我们只能到达s倍数的点
所以要特殊处理咯
下面贴代码
#include<cstdio> #include<cstring> #include<algorithm> #define min(a,b) (a)<(b)?(a):(b) using namespace std; int num[105]; bool stone[11105]; int dp[11105]; int ans=121,l,s,t,m; int main(){ scanf("%d%d%d%d",&l,&s,&t,&m); for(int i=1;i<=m;i++)scanf("%d",&num[i]); num[0]=0;num[m+1]=l; sort(num+1,num+m+1); if(s==t) { int tot=0; for(int i=1;i<=m;i++) if(!(num[i]%s))tot++; printf("%d\n",tot); } else{ int k=s*t,move=0; for(int i=1;i<=m+1;i++) { int x=num[i]-move-num[i-1]; if(x>k)move+=x-k; num[i]-=move; stone[num[i]]=true; } stone[num[m+1]]=false; memset(dp,127,sizeof(dp)); dp[0]=0; for(int i=1;i<=num[m+1]+t-1;i++) { for(int j=s;j<=t;j++) if(i>=j)dp[i]=min(dp[i],dp[i-j]); dp[i]+=stone[i]; } for(int i=num[m+1];i<=num[m+1]+t-1;i++) ans=min(ans,dp[i]); printf("%d\n",ans); } }
原文：http://www.cnblogs.com/ghostfly233/p/6995445.html