这个问题可以使用
动态规划方法解决。
我们会递归地将整个任务缩小为子任务。对于数组中的每个位置
,如果我们被允许修改个元素,就让我们构建一个数组,它表示A [0..i]
的子任务和自定义k0
值的答案是什么。有一个例外-d [i] [k0]
提供了在不改变A [i]
的情况下的最优解。
现在,如果我们知道更小的 i 的所有答案,就可以为d [i] [k0]
构建一个答案。请记住,根据定义,A [i]
不会改变。这意味着我们可以构建一个更改值的段 A [l + 1..i-1]
(这里 segment_len = i-l-1
),再加上使用答案 d [l] [k0-segment_len]
,从这两个中,我们可以看出 d [i] [k0]
是 d [l] [k0-segment_len]
和更改段内的最小差异。我们可以看到,通过取步长等于(last-first + segment_len-1)/ segment_len
,可以最优地构建片段。
现在遍历所有段的长度,我们可以找到可能的最小 d [i] [k0]
。整个任务的最终答案是 d [n] [k]
。
我认为更好的优化是可能的,但我通过3个嵌套循环解决了这个动态规划任务。如果我给我的代码随机输入,它会在
n = 1000, k = 500
时在1秒钟内返回答案,在
n = 2000, k = 1000
时在8秒钟后返回答案。
我甚至有想法如何大大加速它。但如果我有时间的话,可能以后再实现它们。
因此,我的算法的时间复杂度是
O(n * k^2)
,空间复杂度是
O(n * k)
。
在线尝试!
#include <cstdint>
#include <vector>
#include <limits>
using i32 = int32_t;
i32 Solve(std::vector<i32> const & A, i32 n, i32 k) {
std::vector<std::vector<i32>> d(n + 1, std::vector<i32>(k + 1));
for (i32 i = 0; i <= n; ++i)
for (i32 k0 = 0; k0 <= k; ++k0) {
i32 rmin = std::numeric_limits<i32>::max();
for (i32 j = 0; j <= k0; ++j) {
i32 r = 0;
if (i - 1 - j < 0)
r = 0;
else if (i >= n)
r = d[i - 1 - j][k0 - j];
else {
i32 step = (std::abs(A[i] - A[i - 1 - j]) + j) / (j + 1),
prev = d[i - 1 - j][k0 - j];
r = std::max(step, prev);
}
rmin = std::min(rmin, r);
}
d[i][k0] = rmin;
}
return d[n][k];
}
#include <random>
#include <chrono>
#include <iomanip>
#include <iostream>
void Test() {
auto Time = []{
static auto const gtb = std::chrono::high_resolution_clock::now();
return std::chrono::duration_cast<std::chrono::duration<double>>(
std::chrono::high_resolution_clock::now() - gtb).count();
};
std::mt19937_64 rng{std::random_device{}()};
std::uniform_int_distribution<i32> distr(-1'000'000'000, 1'000'000'000);
i32 n = 1'000, k = 500;
std::vector<i32> A(n);
for (size_t i = 0; i < A.size(); ++i)
A[i] = distr(rng);
auto tim = Time();
i32 res = Solve(A, n, k);
tim = Time() - tim;
std::cout << "Result " << res << ", time " << std::fixed
<< std::setprecision(4) << tim << " sec" << std::endl;
}
int main() {
Test();
}
输出:
Result 295187479, time 1.0335 sec
k
次更改中实现绝对差为m
。 对于每个数组前缀A [0..i]
和值v
,编写一个动态规划公式,以获得“A [0..i]
需要的更改次数,以使其绝对差最多为m
,假设A [0..i]
将以A [i] = v
结尾”。 - kcsquaredA[0..i]
以A[i]=v
结尾”。这不是给定的。取A=[28,42,37,...]
,m=10
。当i=0
时,不需要进行任何更改。当i=1
时,A[0..1]
包含一个差值为14
的元素。我们可以将A[0]=42
或A[1]=32..52
。但是我们没有下一次迭代所需的A[1]
。更糟糕的是,我们可能会同时更改A[0]
和A[1]
(例如A=[28,42,37,1000,1000,1000,1000]
)。我认为动态规划无法解决这个问题。 - Jojonete