arrays - 如何找到最小编号。通过选择任何间隔并在每一步将“1”添加到间隔中的所有项目来使数组不递减的步骤？

Question

给定一个数组，我们需要找到可以使它不递减的最小步数。我们可以选择 i & j 并在每个步骤中为区间 a[i] 到 a[j]（包括两者）中的所有元素添加 '1'

for eg: A={3,2,1}
        answer is 2.
        step1 : {3,3,2} i=1,j=2
        step2 : {3,3,3} i=2,j=2

我认为它可以使用 DP 解决，但想不到它......请帮助

Answer 1

这个问题可以通过一个技巧来解决，这个技巧在观察时是有用的。我所做的是找到主数组的所有严格递减的子数组，并减去它们的第一个和最后一个元素（最高-最低）并添加。结果是所需的最少步骤。

int min_step(int arr[],int n)
{
    int step=0,max=arr[0];
    for(int i=1;i<n;i++)
    {
        if(i==x || arr[i]>=arr[i-1]);
        {
            step+=(max-arr[i-1]);
            max=arr[i];
        }
    }
    return step;
}

例如。如果我将数组设为：

arr[4]={11,8,4,54}

答案是 7。（如何？）

11 8 4 54
Choosing {8,4} and increasing 3 times
11 11 7 54
Choosing {7} and increasing 4 times
11 11 11 54
Which is the required array

该算法通过使用唯一的递减子数组 (11,8,4) 和 11-4=7 来计算相同的答案

这是因为如果我们找到递减的子数组，则首先对最小元素旁边的元素进行平整，然后增加递增的范围。