题解

Difficulty: 3.5 / Easy

Tag: -

首先有个朴素的 DP：$dp[i]=\min_{j=s}^t dp[i-j]+[i\in A]$。

但是注意到如果石头间间隔很远，可以随便跳，前面的石头位置已经不影响后面怎么跳了。

这个距离大概是多少呢？

根据小凯的疑惑，在 $ab-a-b+1$ 及以后的数都可以用 $ax+by$ 表示。所以如果 $t-s\ge 1$，且 $[l,r]$ 没有石头，从 $[l,r-s(s-1)]$ 间所有点都可以跳到 $r$。所以这个距离设置成 $2s(s-1)+t$ 是完全够用的。

这样 DP 总长度就缩小到 $O(ns^2)$ 了。复杂度为 $O(ns^3)$。

当然，你可以通过 $(\min,+)$ 矩阵乘法等方式求出距离为 $1\sim 2s(s-1)+t$ 的 DP 长什么样，优化成 $O(s^5+ns^2)$ 或 $O(s^3\log s+ns^2\log s)$ 之类的。但 $n$ 这么小，感觉也没啥必要优化。

注意特判 $s=t$ 的情况。

namespace cjdst{
	void solve(){
		int n, m, s, t;
		std::cin >> m >> s >> t >> n;
		std::vector <int> a(n + 5);
		for(int i = 1; i <= n; i++){
			std::cin >> a[i];
		}
		std::sort(a.begin() + 1, a.begin() + n + 1);
		if(s == t){
			int ans = 0;
			for(int i = 1; i <= n; i++){
				if(a[i] % s == 0) ans++;
			}
			std::cout << ans << '\n';
			return;
		}
		int dis = s * (s - 1) * 2 + t;
		auto solve2 = [=](int l, int r){
			std::vector <int> b(a[r] - a[l] + dis + t + 5);
			for(int i = l; i <= r; i++){
				if(a[l] < dis) b[a[i]] = 1;
				else b[a[i] - a[l] + dis] = 1;
			}
			std::vector <int> dp(a[r] - a[l] + dis + t + 5, 0x3f3f3f3f);
			dp[0] = 0;
			for(int i = 1; i <= a[r] - a[l] + dis + t + 1; i++){
				for(int j = s; j <= t; j++){
					if(i >= j) dp[i] = std::min(dp[i], dp[i - j] + b[i]);
				}
			}
			return dp[a[r] - a[l] + dis + t + 1];
		};
		int l = 1, ans = 0;
		for(int i = 2; i <= n; i++){
			if(a[i] - a[i - 1] > dis){
				ans += solve2(l, i - 1);
				l = i;
			}
		}
		ans += solve2(l, n);
		std::cout << ans << '\n';
	}
}

时间复杂度：$O(ns^3)$。