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

Question

给定一个数组，我们需要找到使其不递减的最小步数。我们可以选择i&j，并在每一步将区间ai中的所有元素加上'1‘到一个j

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解决，但不能想到it......plz帮助

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来计算相同的答案

这是因为如果我们找到了递减的子数组，那么最小的元素旁边的元素首先被平整，然后递增的范围随后增加。