Как найти минимальное число. шагов, чтобы сделать массив неубывающим, выбрав любой интервал и добавив «1» ко всем элементам в интервале на каждом шаге?

Учитывая массив, нам нужно найти минимальное количество шагов, за которое мы можем сделать его неубывающим. Мы можем выбрать i и j и добавить «1» ко всем элементам в интервале от a [i] до a [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, но я не могу об этом думать ...... помогите, пожалуйста


arrays sorting dynamic-programming lcs
person ujjawal kumar    schedule 25.03.2014    source источник
comment
Вы уверены в том, что вы можете сделать на каждом этапе? Я не могу придумать причину, по которой у вас не всегда будет j как максимальное значение, и в этом случае это просто вопрос добавления различий при уменьшении последовательных элементов.   -  person The Dark    schedule 26.03.2014
comment
Я думаю, вам нужно проделать еще много работы здесь, прежде чем мы сможем вам помочь. По крайней мере, опубликуйте код, чтобы показать, что вы что-то пробовали.   -  person James King    schedule 06.04.2014

Ответы (1)


arrow_upward
1
arrow_downward

Задачу можно решить с помощью трюка, который оказывается полезным при наблюдении. Что я делаю, так это нахожу все строго убывающие подмассивы основного массива, вычитаю их первый и последний элементы (самый высокий-самый низкий) и добавляю. В результате требуется минимальное количество шагов.

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.

Это работает за счет того, что если мы находим убывающий подмассив, то сначала выравнивается элемент, следующий за самым маленьким элементом, а затем последовательно увеличивается диапазон возрастания.

person rjalfa    schedule 14.09.2014