https://www.luogu.org/problem/show?pid=1052
观察数据，L到10^9，就是O(n)也不可以。 然后再观察数据，发现共才100个石子，对于桥的长度来说石子非常稀疏，中间有一大块空白区域。 状态转移方程： f[i]=min(f[i],f[i-j]+v[i]); 发现，f[i]的状态只跟f[i-t]~f[i-s]有关，所以中间会有一大块区域无用（可以这么说），于是就考虑到将无用的部分可以去掉，就用到了状压dp； 因为状态转移方程中的f[i]只跟前面长度为t的一段有关，而且只会影响长度为t的一段。 处理方法，将石子之间长度d[i]大于d[i]%t+t的，压缩为d[i]%t+t; 注意的问题：因为青蛙不是正好跳到L，所以要处理到L+t-1 贴上代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> #include<string> #include<map> #define LL long long using namespace std; int l,s,t,m; int a[110],f[111*200],v[111*200]; int d[111]; int main() { memset(f,127,sizeof(f)); 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]; for(int i=1;i<=m;i++) { if(d[i]<=t+d[i]%t) a[i]=a[i-1]+d[i]; else a[i]=a[i-1]+d[i]%t+t; v[a[i]]=1; } l=(l-a[m])%t+t+a[m]; memset(f,127,sizeof(f)); f[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(!v[i]) f[i]=min(f[i],f[i-j]); else f[i]=min(f[i],f[i-j]+1); } int ans=200; for(int i=l;i<=l+t-1;i++) ans=min(ans,f[i]); printf("%d\n",ans); return 0; }