洛谷 P1052 过河

题目传送门

方程很好推,f[当前点]=min{f[能一步到这个点的点]+(1或0)}.30分到手.

但是对于100分做法,长度太长,数组开不起,所以要想办法优化.看到最多一步跳t个距离,所以两个石子的中间可能隔着非常长的一段空区间(对答案没啥用),所以我们就要把这些减掉.

每两个相邻的石子之间减去(kt),使其距离x满足(t leq x_i<2t).

注意:最后我们可能不一定非常准确的跳到l上,所以统计答案要从l~l+t-1中找.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int l,s,t,m,a[101],d[105],k,f[100001],ans = 60000,cs;
bool vis[101000];

inline bool cmp(int whk,int oi) {
	return whk < oi;
}

int main() {
	memset(f,0x3f,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,cmp);
 	for(int i = 1;i <= m; i++) {
		d[i] = a[i] - a[i-1];
		d[i] = d[i] % t;
	}
	d[m+1] = l - a[m];
	d[m+1] = d[m+1] % t;
	for(int i = 1;i <= m + 1; i++) {
		if(a[i]-a[i-1] >=t) d[i] += t;
		k = k + d[i];
		vis[k] = 1;
	}
	f[0] = 0;
	vis[k] = 0;
	for(int i = 0;i <= k + t; i++)
		for(int j = max(0,i - t);j <= i - s; j++)
			if(vis[i])
				f[i] = min(f[j] + 1,f[i]);
			else 	
				f[i] = min(f[i],f[j]);
	for(int i = k;i <= k + t; i++)
		ans = min(ans,f[i]);
	printf("%d",ans);
	return 0;
}