题解
2026-06-21 22:12:46
发布于:广东
6阅读
0回复
0点赞
Difficulty: 3.5 / Easy
Tag: -
首先有个朴素的 DP:。
但是注意到如果石头间间隔很远,可以随便跳,前面的石头位置已经不影响后面怎么跳了。
这个距离大概是多少呢?
根据小凯的疑惑,在 及以后的数都可以用 表示。所以如果 ,且 没有石头,从 间所有点都可以跳到 。所以这个距离设置成 是完全够用的。
这样 DP 总长度就缩小到 了。复杂度为 。
当然,你可以通过 矩阵乘法等方式求出距离为 的 DP 长什么样,优化成 或 之类的。但 这么小,感觉也没啥必要优化。
注意特判 的情况。
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';
}
}
时间复杂度:。
全部评论 1
我的精神状态:这题是不是可以矩乘,但是复杂度劣爆了,但是好玩,那我高低得写一下,诶等等这是不是真可以优化原来的 DP,我去原来有用啊,那我懒得写了
2天前 来自 广东
0





有帮助,赞一个