复习复习DP。。。都忘了QAQ...
好了这道题我其实是看题解才会的。。。
方程 f[i]=min(f[i-j]+v[i]) v[i]表示i是不是石头 s<=j<=t
路径压缩引用一下证明From Luogu@Panda_Hu
#include<cstdio>
#include<iostream>
#define R register int
#include<algorithm>
#define R register int
const int N=,Inf=0x3f3f3f3f;
using namespace std;
int l,t,s,n,mn=Inf,ans=Inf;
int a[N],f[N],d[N],v[N];
inline int g() {
R ret=,fix=; register char ch; while(!isdigit(ch=getchar()));
do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret;
}
inline int min(int a,int b) {return a<b?a:b;}
signed main() {
l=g(),s=g(),t=g(),n=g();
if(s==t) { R cnt=; for(R i=,x;i<=n;++i) x=g(),cnt+=(x%s==);
printf("%d\n",cnt); return ;
} for(R i=;i<=n;++i) a[i]=g(); sort(a+,a+n+); d[n+]=min(l-a[n],); l=;
for(R i=;i<=n;++i) d[i]=min(a[i]-a[i-],),l+=d[i],v[l]=; l+=d[n+];
for(R i=;i<=l+;++i) { f[i]=Inf;
for(R j=s;j<=t;++j) if(i>=j) f[i]=min(f[i],f[i-j]+v[i]);
} for(R i=l;i<l+;++i) ans=min(ans,f[i]); printf("%d\n",ans);
}
2019.04.28 慌得一批QAQ