状压DP QAQ 看这个题目啊，还是蛮简单的吧 很显然DP方程为dp[i]=min(dp[i],dp[i-j]) 如果有石子，这个DP要+1的 可是这个范围，1e9，，，，，，，，，， 我很无奈啊，这咋办，我就是想水个题啊 看一下数据范围，m<=100也就是说，石子很稀疏，恩，很重要的信息 现在我们想一下，如果很长的一段区间之间内没有石子，我们的DP没有啥意义 这是一些不断的重新copy 于是我们的做法就是把石子的距离减小 从而达到快速的目的
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> using namespace std; int dp[99999]; int d[99999]; int a[99999]; int ss[99999]; int k[9999]; int main() { int l,s,t,m; scanf("%d%d%d%d",&l,&s,&t,&m); for(int i=1;i<=m;i++) scanf("%d",&a[i]); sort(a+1,a+m+1); for(int i=1;i<=m;i++) { d[i]=a[i]-a[i-1]; k[i]=d[i]%t; } for(int i=1;i<=m;i++) { if(d[i]<=t+k[i]) a[i]=a[i-1]+d[i]; else a[i]=a[i-1]+t+k[i]; ss[a[i]]=1; } int p=(l-a[m])%t; l=a[m]+t+p; memset(dp,0x7f,sizeof(dp)); dp[0]=0; for(int i=1;i<=l+t-1;i++) { for(int j=s;j<=t;j++) if(i-j>=0 && i-j<l) { if(!ss[i]) dp[i]=min(dp[i],dp[i-j]); else dp[i]=min(dp[i],dp[i-j]+1); } } int ans=1e7; for(int i=l;i<=l+t-1;i++) ans=min(dp[i],ans); printf("%d",ans); return 0; }