你会得到一个位于x轴上的城市。它有n座建筑物。第一座建筑位于 x = 1 中，高度为 h1，第二座建筑位于 x = 2 且高度为 h2，依此类推。你是一个巨大的怪物，拿着一把剑，想要摧毁这座城市。你本质上也是一个计算机科学家，所以你的效率是关键，因此你想用最少的移动次数摧毁城市。
您可以执行以下两个动作之一：
1. 从 x = L 到 x = R进行水平切割，将建筑物的高度从 x = L 到 X = R 切割 1。
2. 在 x = P 处进行垂直切割，在 x = P 处完全摧毁建筑物，从而使其高度为零。**
请注意：对于第一种类型的移动，从L到R范围内的每个城市必须至少剩余1个高度，即你不能穿过空白区域。
打印摧毁城市所需的最小移动次数。
输入
第一行包含测试用例的数量。 对于每个测试用例，第一行包含建筑物 n 的数量。 第二行包含表示建筑物高度的 n 个整数
输出
对于每个测试用例，在新行上打印摧毁城市的最小移动次数。
笔记
1 ≤ n ≤ 1000 0 ≤ hi ≤ 1000
样本输入 0
阿拉伯数字
5
2 22 3 3
5
10 2 102 10
样本输出 0
3
5
我无法弄清楚这个问题的方法。我的代码不适用于以下输入： 1 1 1 2 4 5 7 7 8 9** 在我的代码中，我减少了所有元素的最小值。然后找出零之间的子数组，然后将子数组(j-i(的长度与最小值进行比较。如果长度较小，那么我们需要遵循移动 2，否则移动 1。 我的代码：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.Scanner;
public class Main {
static int findmin(int arr[], int i, int j) {
int min = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
if (min > arr[k]) {
min = arr[k];
}
}
return min;
}
static void subtractmin(int arr[], int i, int j, int min) {
//if both the length of subarray and min are equal, we destroy separately
if (j - i <= min) {
for (int k = i; k < j; k++) {
// if
arr[k] = 0;
}
} else {
//subtract all
for (int k = i; k < j; k++)
// if
{
arr[k] -= min;
}
}
}
public static void main(String[] args) {
//int input[] = {10, 2, 10, 2, 10};// 5
//int input[] = {2, 2, 2, 3, 3};// 5
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- != 0) {
int zeros = 0;
int n = sc.nextInt();
int input[] = new int[n];
int min = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
input[i] = sc.nextInt();
if (min > input[i]) {
min = input[i];
}
if (input[i] == 0) {
zeros++;
}
}
//subtract minimum element from array
int count = 0;
if (zeros == 0) {
count += min;
subtractmin(input, 0, n, min);
} else {
count += min;
subtractmin(input, 0, n, min);
}
//traverse the array and findsubarrays between 0's
//1) if an element is surrounded by 0's it will be destroyed at once separately
// 2) also if length of subarray<min element, they all need to be destroyed separately
// 3) if min<length of subarray they need to be destroyed at once with count+=min
int i = 0, j = 0;
while (true) {
//move i to the first non zero element
for ( i = 0; i < n; i++) {
if (input[i] != 0) {
break;
}
}
//means whole array is 0;
if (i == n) {
System.out.println(Math.min(count, n - zeros));
break;
}
///start with the first non zero element and fin
for (j = i; j <= n; j++) {
if ( j == n || input[j] == 0) {
// take out min element
int minEle = findmin(input, i, j) ;
//if min lement is greater than subarray size, destroy separately
count += Math.min(minEle, j - i);
//System.out.println("count="+count+"min element="+minEle);
// subtract minimum element
subtractmin(input, i, j, minEle);
}
//if last elemnt is not zero
}
}
}
}
}
这里一个可能的提示是，将建筑物减少到零会分隔部分，这意味着分而治之。
让我们f(A, l, r)表示在[l, r]处索引的A部分的最佳移动次数。然后：
f(A, l, r):
min(
# Reduce the whole section
# without separating it, using
# move 1, the horizontal cuts.
max(A[l..r]),
# Divide and conquer
1 + f(A, l, k-1) + f(A, k+1, r)
)
for all l ≤ k ≤ r
除了我们不需要尝试所有k，只需要一个指向max(A)。不删除max(A)意味着我们需要执行max(A)动作，或者我们以后必须删除它。
JavaScript 代码：
function findMax(A, l, r){
let idx = l;
for (let i=l; i<=r; i++)
if (A[i] > A[idx])
idx = i;
return idx;
}
function f(A, l=0, r=A.length-1, memo={}){
if (l > r)
return 0;
if (l == r)
return 1;
const key = String([l, r]);
if (memo.hasOwnProperty(key))
return memo[key];
const k = findMax(A, l, r);
const best = Math.min(A[k], 1 + f(A, l, k-1, memo) + f(A, k+1, r, memo));
return memo[key] = best;
}
var As = [
[2, 2, 2, 3, 3],
[10, 2, 10, 2, 10],
[1, 1, 1, 2, 4, 5, 7, 7, 8, 9]
];
for (let A of As)
console.log(f(A));你遇到的问题不在于代码，而在于算法。 如果段的大小足够小，则必须有效地执行移动 2。但是，这个条件并不是不可或缺的。
在实践中，一个简单的递归方法可以解决这个问题。在给定的段 [k， l] 中，在减去最小值后，您只需执行：
n_moves = min (n, vmin + min_moves(x, k, l));
在下文中，一个函数检测零的位置，并对对应于每个段的移动求和 并为每个段调用另一个函数，内部没有零。
以下代码是C++的，但它相当简单，应该很容易翻译成另一种语言。
输出：
1 2 7 : 3
2 2 2 3 3 : 3
10 2 10 2 10 : 5
1 1 1 2 4 5 7 7 8 9 : 8
提供此代码是为了完整起见。重要的是算法本身。
#include <iostream>
#include <vector>
#include <algorithm>
std::vector<int> get_zeros (const std::vector<int> &x, int k, int l) {
std::vector<int> zeros;
for (int i = k; i <= l; ++i) {
if (x[i] == 0) zeros.push_back(i);
}
return zeros;
}
int min_moves (std::vector<int> &x, int k, int l);
// This function is called after detection the position of the zeros -> no zero inside
int min_moves_no_zero (std::vector<int> &x, int k, int l) {
int n = l-k+1;
if (n == 0) return 0;
if (n == 1) return 1;
int vmin = 10000;
for (int i = k; i <= l; ++i) {
if (x[i] < vmin) vmin = x[i];
}
for (int i = k; i <= l; ++i) {
x[i] -= vmin;
}
int nm = std::min (n, vmin + min_moves(x, k, l));
return nm;
}
// This function detects positions of the zeros and sum the moves corresponding to each segment
int min_moves (std::vector<int> &x, int k, int l) {
auto zeros = get_zeros (x, k, l);
if (zeros.size() == 0) return min_moves_no_zero (x, k, l);
int start = k;
int total = 0;
for (int z = 0; z < zeros.size(); ++z) {
int end = zeros[z] - 1;
if (start != zeros[z]) {
total += min_moves_no_zero (x, start, end);
}
start = end + 2;
}
if (start <= l) {
total += min_moves_no_zero (x, start, l);
}
return total;
}
void print (const std::vector<int> &x) {
for (auto k: x) {
std::cout << k << " ";
}
}
int main() {
std::vector<std::vector<int>> input {
{1, 2, 7},
{2, 2, 2, 3, 3},
{10, 2, 10, 2, 10},
{1, 1, 1, 2, 4, 5, 7, 7, 8, 9}
};
for (auto& arr: input) {
auto save = arr;
int moves = min_moves (arr, 0, arr.size()-1);
print (save);
std::cout << " : " << moves << "n";
}
}