给定 n 个柱状图的排序直方图，选择 k 个柱状图，同时最小化右壁封闭的区域
Given a sorted histogram of n bars, pick k bars while minimising the area enclosed with right wall
给定一个整数 k 和一个带有 n 条高度 a1, a2, a3,..., an 的排序直方图（该序列是非递减的，因为直方图已排序）。我们必须从这些 n 根柱中挑选出 k 根柱（1 <= k <= n），以使所选柱与直方图右壁之间封闭的区域尽可能小。
例如，对于高度序列 {1, 3, 5, 9}，如果我们选择高度为 1, 5 的柱；右墙包围的区域将是 12 个单位，看起来像图像中的样子（假设条的宽度为 1 个单位。）
在尝试了一些贪婪的方法（这是错误的）之后，我转向了以下动态规划解决方案：
将 dp[i][j][last] 定义为从直方图中的前 i 根柱中挑选 j 根柱时的最小面积，这样我们右边的前一根柱有一个索引 last.
dp[i][j][last] = min(dp[i - 1][j][last], dp[i - 1][j - 1][i] + a[i] * (last - i));
但问题是它太慢了，它的O(n2k)，所以我希望有人能帮忙我将其优化为 O(nk) 之类的东西，或者建议一些更快的贪婪解决方案。
在下文中，我将假设 k >= 2，否则问题很容易解决。
这是一个部分解决方案，从某种意义上说，如果条形具有某些特定属性，它可以在 O(n) 时间内解决一些问题。
具体我们可以推断如下：
如果所有柱体覆盖的体积是凸的，那么最优解只包含开始和结束的柱体。
证明：
假设解中存在任何分裂，那么我们可以将远离其中一条边的组移向其中一条边。这是通过在一侧 deselecting 一个 bar 并在另一侧 selecting 一个新的 bar 来完成的。由于形状是凸的，曲率必须是 non-positive，然后当我们在 non-increasing 方向移动时，在该方向进一步移动的减少必须至少同样大（曲率确保这一点）。因此，我们可以将解决方案中的拆分移动到边缘之一，而不增加（并且可能减少）覆盖的区域。
我们可以在 O(n) 时间内检查形状是否凸起（条之间存在 non-increasing 差异），我们可以通过滑动 window 优化来解决问题，这在 O(n) 中很容易做到。因此，我们可以用它预处理任何其他解决方案，以将问题集减少为至少包含一个凹区域的问题。如果我们能找到其他算法的子问题也包含这个属性，那么我们也可以在这个意义上单独解决这些问题。
对于凹形区域，除了外部可能的稳定区域（其他分裂仍可能被吸引，因为即使面积不同在这样的举动上是积极的，举动可能仍然是消极的）。使用这个我们可以通过分段来描述一个完全凹的区域，其中分裂将向边缘或稳定的中点移动。
请注意，当凹凸区域连接时，上述大部分情况都会下降，因为稳定性标准取决于我们测量的起点和终点是否存在边界。虽然可以通过构建这种方法来解决全部问题，但我不确定它对任意复杂的形状有多大帮助。
尽管（在全球范围内）对凹区域具有内部稳定区域的要求往往相当苛刻，但我不确定您是否可以在全球范围内获得很多这样的区域，所以这是一种算法，它根据问题的复杂性，通过不同的启发式方法进行筛选并传递给如果我们不确定是否找到了最佳解决方案，价格会更高。
首先我们计算基本结果，以滑动 window 方式 (O(n)) 并保存该结果。然后我们寻找单个点的稳定区域（那些外部区域已经通过滑动 window 考虑在内）远离边缘，并且面积小于找到的解决方案。如果有超过 1 个这样的点（需要特殊形状），则默认返回基本算法，如 Manish Chandra Joshi 的算法。如果找到一个这样的点，我们继续 O(nk) 解决方案，如果 none，则接受当前解决方案。请注意，我们可以将下面的版本扩展到超过 1 个这样的全局稳定性点，但实际上它要求它们相当接近，否则它们以后往往会作为故障出现。
在 'O(kn)' 解决方案中，我们在中间全局稳定点的两侧分别解决滑动 window，对于每个 k 可能的赋值量两侧都有障碍，select 是这些解决方案中最好的。然后我们再次在每个区域中寻找稳定区域（记住，这意味着分裂不会向边缘移动），并检查这些点的最佳区域是否与我们正在计算的中心点一起for 的面积低于 'O(kn)' 和 'O(n)' 解中较小的一个。如果找到这样的点，我们必须解决一个完整的解决方案（如 Manish Chandra Joshi 的），否则我们可以接受我们计算出的 2 个解决方案中最好的一个。
请注意，在上述算法中，应该可以包含一个安全的或容易从安全解决方案导出的更大边界区域，从而增加我们不回退到较慢算法的情况的数量。特别是距离边缘大约 'k' 的区域可能有简单的解决方案，或者实际上已经被早期的解决方案所覆盖。请注意，将滑动 windows 计算为 non-covered 区域的 windows，当结合 'O' 中的动态规划解决方案的数据时，我们应该能够为这种情况生成一些简单的解决方案(kn)` 例。
Ninetails 的部分解决方案涵盖了部分答案，我想出了其他几个我将分享的案例。
我没有这方面的证据，但我们采用的最佳柱形总是形成 1010 或 10 或 01 或 010 或101 或琐碎的 1。 （这里 1 表示我们采用的一系列柱，0 表示我们没有采用的一系列柱）
这意味着最佳条总是在一个连续的组中或两个连续的组中，其中一组触及最左边。我已经使用带有 O(2nn2) brute-force 和 O(n2k) 由运行动态规划解决几千个案例。
因此，有了这种洞察力，我们可以使用前缀和数组轻松地在 O(n * k) 中找到答案，从而有效地找到范围和。这是 C++ 中的最终代码（带有少量注释）
using ll = long long;
ll n, z;
cin >> n >> z;
vector<ll> a(n);
for (auto &e : a) {
cin >> e;
}
assert(is_sorted(a.begin(), a.end()));
ll stratAns, ans = INF;
// prefix sum array
vector<ll> pref(n + 1);
for (int i = 1; i <= n; ++i) {
pref[i] = pref[i - 1] + a[i - 1];
}
stratAns = INF;
/// strategy 1 : handles cases where runs like 10, 01, 010, 1 are optimal to choose
for (int starting = 0; starting + z - 1 < n; ++starting) {
int ending = starting + z - 1;
ll curAns = 0;
//~ for (int i = starting; i <= ending; ++i) {
//~ curAns += a[i];
//~ }
// doing the same with prefix sums instead
curAns += pref[ending + 1] - pref[starting];
curAns += a[ending] * (n - ending - 1);
stratAns = min(stratAns, curAns);
}
ans = min(ans, stratAns);
stratAns = INF;
/// strategy 2 : handle cases when runs 1010 and 101 are optimal
for (int last = z - 1; last < n; ++last) {
for (int x = 1, y = z - 1; y > 0 && x < z; x++, y--) {
assert(x + y == z);
ll curAns = 0;
//~ for (int i = 0; i < x; ++i) {
//~ curAns += a[i];
//~ }
// performing the same with prefix sums instead
curAns += pref[x];
curAns += a[x - 1] * (last - y + 1 - x);
//~ for (int i = last - y + 1; i <= last; ++i) {
//~ curAns += a[i];
//~ }
// performing the same with prefix sums instead
curAns += pref[last + 1] - pref[last - y + 1];
curAns += a[last] * (n - last - 1);
stratAns = min(curAns, stratAns);
}
}
ans = min(ans, stratAns);
cout << ans << endl;
给定一个整数 k 和一个带有 n 条高度 a1, a2, a3,..., an 的排序直方图（该序列是非递减的，因为直方图已排序）。我们必须从这些 n 根柱中挑选出 k 根柱（1 <= k <= n），以使所选柱与直方图右壁之间封闭的区域尽可能小。
例如，对于高度序列 {1, 3, 5, 9}，如果我们选择高度为 1, 5 的柱；右墙包围的区域将是 12 个单位，看起来像图像中的样子（假设条的宽度为 1 个单位。）
在尝试了一些贪婪的方法（这是错误的）之后，我转向了以下动态规划解决方案：
将 dp[i][j][last] 定义为从直方图中的前 i 根柱中挑选 j 根柱时的最小面积，这样我们右边的前一根柱有一个索引 last.
dp[i][j][last] = min(dp[i - 1][j][last], dp[i - 1][j - 1][i] + a[i] * (last - i));
但问题是它太慢了，它的O(n2k)，所以我希望有人能帮忙我将其优化为 O(nk) 之类的东西，或者建议一些更快的贪婪解决方案。
在下文中，我将假设 k >= 2，否则问题很容易解决。
这是一个部分解决方案，从某种意义上说，如果条形具有某些特定属性，它可以在 O(n) 时间内解决一些问题。
具体我们可以推断如下：
如果所有柱体覆盖的体积是凸的，那么最优解只包含开始和结束的柱体。
证明：
假设解中存在任何分裂，那么我们可以将远离其中一条边的组移向其中一条边。这是通过在一侧 deselecting 一个 bar 并在另一侧 selecting 一个新的 bar 来完成的。由于形状是凸的，曲率必须是 non-positive，然后当我们在 non-increasing 方向移动时，在该方向进一步移动的减少必须至少同样大（曲率确保这一点）。因此，我们可以将解决方案中的拆分移动到边缘之一，而不增加（并且可能减少）覆盖的区域。
我们可以在 O(n) 时间内检查形状是否凸起（条之间存在 non-increasing 差异），我们可以通过滑动 window 优化来解决问题，这在 O(n) 中很容易做到。因此，我们可以用它预处理任何其他解决方案，以将问题集减少为至少包含一个凹区域的问题。如果我们能找到其他算法的子问题也包含这个属性，那么我们也可以在这个意义上单独解决这些问题。
对于凹形区域，除了外部可能的稳定区域（其他分裂仍可能被吸引，因为即使面积不同在这样的举动上是积极的，举动可能仍然是消极的）。使用这个我们可以通过分段来描述一个完全凹的区域，其中分裂将向边缘或稳定的中点移动。
请注意，当凹凸区域连接时，上述大部分情况都会下降，因为稳定性标准取决于我们测量的起点和终点是否存在边界。虽然可以通过构建这种方法来解决全部问题，但我不确定它对任意复杂的形状有多大帮助。
尽管（在全球范围内）对凹区域具有内部稳定区域的要求往往相当苛刻，但我不确定您是否可以在全球范围内获得很多这样的区域，所以这是一种算法，它根据问题的复杂性，通过不同的启发式方法进行筛选并传递给如果我们不确定是否找到了最佳解决方案，价格会更高。
首先我们计算基本结果，以滑动 window 方式 (O(n)) 并保存该结果。然后我们寻找单个点的稳定区域（那些外部区域已经通过滑动 window 考虑在内）远离边缘，并且面积小于找到的解决方案。如果有超过 1 个这样的点（需要特殊形状），则默认返回基本算法，如 Manish Chandra Joshi 的算法。如果找到一个这样的点，我们继续 O(nk) 解决方案，如果 none，则接受当前解决方案。请注意，我们可以将下面的版本扩展到超过 1 个这样的全局稳定性点，但实际上它要求它们相当接近，否则它们以后往往会作为故障出现。
在 'O(kn)' 解决方案中，我们在中间全局稳定点的两侧分别解决滑动 window，对于每个 k 可能的赋值量两侧都有障碍，select 是这些解决方案中最好的。然后我们再次在每个区域中寻找稳定区域（记住，这意味着分裂不会向边缘移动），并检查这些点的最佳区域是否与我们正在计算的中心点一起for 的面积低于 'O(kn)' 和 'O(n)' 解中较小的一个。如果找到这样的点，我们必须解决一个完整的解决方案（如 Manish Chandra Joshi 的），否则我们可以接受我们计算出的 2 个解决方案中最好的一个。
请注意，在上述算法中，应该可以包含一个安全的或容易从安全解决方案导出的更大边界区域，从而增加我们不回退到较慢算法的情况的数量。特别是距离边缘大约 'k' 的区域可能有简单的解决方案，或者实际上已经被早期的解决方案所覆盖。请注意，将滑动 windows 计算为 non-covered 区域的 windows，当结合 'O' 中的动态规划解决方案的数据时，我们应该能够为这种情况生成一些简单的解决方案(kn)` 例。
Ninetails 的部分解决方案涵盖了部分答案，我想出了其他几个我将分享的案例。
我没有这方面的证据，但我们采用的最佳柱形总是形成 1010 或 10 或 01 或 010 或101 或琐碎的 1。 （这里 1 表示我们采用的一系列柱，0 表示我们没有采用的一系列柱）
这意味着最佳条总是在一个连续的组中或两个连续的组中，其中一组触及最左边。我已经使用带有 O(2nn2) brute-force 和 O(n2k) 由运行动态规划解决几千个案例。
因此，有了这种洞察力，我们可以使用前缀和数组轻松地在 O(n * k) 中找到答案，从而有效地找到范围和。这是 C++ 中的最终代码（带有少量注释）
using ll = long long;
ll n, z;
cin >> n >> z;
vector<ll> a(n);
for (auto &e : a) {
cin >> e;
}
assert(is_sorted(a.begin(), a.end()));
ll stratAns, ans = INF;
// prefix sum array
vector<ll> pref(n + 1);
for (int i = 1; i <= n; ++i) {
pref[i] = pref[i - 1] + a[i - 1];
}
stratAns = INF;
/// strategy 1 : handles cases where runs like 10, 01, 010, 1 are optimal to choose
for (int starting = 0; starting + z - 1 < n; ++starting) {
int ending = starting + z - 1;
ll curAns = 0;
//~ for (int i = starting; i <= ending; ++i) {
//~ curAns += a[i];
//~ }
// doing the same with prefix sums instead
curAns += pref[ending + 1] - pref[starting];
curAns += a[ending] * (n - ending - 1);
stratAns = min(stratAns, curAns);
}
ans = min(ans, stratAns);
stratAns = INF;
/// strategy 2 : handle cases when runs 1010 and 101 are optimal
for (int last = z - 1; last < n; ++last) {
for (int x = 1, y = z - 1; y > 0 && x < z; x++, y--) {
assert(x + y == z);
ll curAns = 0;
//~ for (int i = 0; i < x; ++i) {
//~ curAns += a[i];
//~ }
// performing the same with prefix sums instead
curAns += pref[x];
curAns += a[x - 1] * (last - y + 1 - x);
//~ for (int i = last - y + 1; i <= last; ++i) {
//~ curAns += a[i];
//~ }
// performing the same with prefix sums instead
curAns += pref[last + 1] - pref[last - y + 1];
curAns += a[last] * (n - last - 1);
stratAns = min(curAns, stratAns);
}
}
ans = min(ans, stratAns);
cout << ans << endl;