假设最后一个格子为 len，跳跃距离为 [s, t]

设 dp[i] 表示最后一步跳到第 i 个格子处经过的最少坏格子数量

则 ans=min(dp[i]) i=len, len+1, ……, len+b-1

len 高达 10^9 ，怎么办？

#include <bits/stdc++.h>
using namespace std;
#define MS 102
#define MAX_space 72  // 最小压缩空间 
#define MAX_Len 10020

int L,S,T,M,ans,Len;
int a[MS],s[MAX_Len],dp[MAX_Len];

int main()
{
	scanf("%d%d%d%d",&L,&S,&T,&M);
	if(S==T) //只能跳固定距离的情况 
	{
		for(int i=1;i<=M;i++)
		{
			scanf("%d",&a[i]);
			if(a[i]%S==0)ans++;
		}
	}
	else // 不是固定距离时进行判断，看能不能状态压缩 
	{
		for(int i=1;i<=M;i++)scanf("%d",&a[i]);
		sort(a+1,a+1+M);
		for(int i=1;i<=M;i++)
		{
			if(a[i]-a[i-1]<=MAX_space) //判断是否可以进行压缩 
			{
				Len+=a[i]-a[i-1];
			}
			else Len+=MAX_space;
			s[Len]=1;
		}
		memset(dp,0x3f,sizeof dp);
		for(int i=S;i<=Len+T-1;i++)
		{
			for(int d=S;d<=T;d++)
				dp[i]=min(dp[i],dp[i-d]);
			dp[i]+=s[i];
		}
		ans=0x3f3f3f3f;
		for(int i=Len;i<=Len+T-1;i++)
			ans=min(ans,dp[i]);			
	}
	printf("%d\n",ans);
}

警钟长鸣

N取值应为102，因为N取了101挂了100分

做法

首先f[i] = f[j] + ok[j]

j >= 0 && i - b >= j >= i - a

然后发现n太大了，然后我们发现格子数很少，考虑把两点之间的距离缩短。

然后lcm(1,2,...,10)=2520,所以说当你在x的时候，无论怎么跳，都可以到x+2520这个点，所以我们把他之间的距离%2520，然后如果说他原本大于2520，膜完之后可能就变得很小，导致有的点原本可以到的但是最终到不了，所以我们要将他加一个2520，然后缩完之后最大的点为（2520+10）*100，这样就可以过了

code

#include <bits/stdc++.h>
using namespace std;

const long long N = 102;//警钟长鸣 

const long long M = 1e6;

long long n, a, b, m, c[N], d[N], f[M], q[M];

void read() {
	cin >> n >> a >> b >> m;
	for(long long i = 1; i <= m; i++) {
		cin >> c[i];
	}
	c[++m] = n;
	sort(c+1,c+1+m);
}

void compute() {
	for(long long i = 1; i <= m; i++) {
		long long w = c[i] - c[i-1];
		if(c[i] - c[i-1] > 2520) {
			w %= 2520;
			w += 2520;
		}
		d[i] = d[i-1] + w;
		if(i != m)
		q[d[i]] = 1;
	}
	long long ans = INT_MAX;
	for(long long i = 1; i <= d[m] + b * 2; i++) {
		f[i] = INT_MAX;
		for(long long j = i - b; j <= i - a; j++) {
			if(j < 0) continue;
			f[i] = min(f[i],f[j]);
		}
		f[i] += q[i];
		if(i >= d[m]) ans = min(ans,f[i]);
	}
	cout << ans;
}

int main() {
	read();
	compute();
	return 0;
}