Рубрики

Предложения храма

Динамическое программирование

Представьте себе преданного, желающего приносить жертвы храмам вдоль горного хребта. Храмы расположены в ряд на разных высотах. Каждый храм должен получить хотя бы одно пожертвование. Если два соседних храма находятся на разных высотах, то храм, который находится выше, должен получать больше приношений, чем тот, который находится ниже. Если два соседних храма находятся на одной высоте, то их предложения относительно друг друга не имеют значения. Учитывая количество храмов и высоту храмов в порядке, найдите минимальное количество предложений, чтобы принести.

Примеры:

Input  : 3
         1 2 2
Output : 4
All temples must receive at-least one offering.
Now, the second temple is at a higher altitude
compared to the first one. Thus it receives one
extra offering. 
The second temple and third temple are at the 
same height, so we do not need to modify the 
offerings. Offerings given are therefore: 1, 2,
1 giving a total of 4.

Input  : 6
         1 4 3 6 2 1
Output : 10
We can distribute the offerings in the following
way, 1, 2, 1, 3, 2, 1. The second temple has to 
receive more offerings than the first due to its 
height being higher. The fourth must receive more
than the fifth, which in turn must receive more 
than the sixth. Thus the total becomes 10.

Мы замечаем, что каждый храм может быть выше, ниже или на том же уровне, что и храм рядом с ним. Подношения, требуемые в каждом храме, равны максимальной длине цепочки храмов на более низкой высоте, как показано на рисунке.

Наивный подход
Чтобы следовать данному правилу, храм должен быть предложен как минимум x + 1, где x — максимум следующих двух.

  1. Количество храмов слева в порядке возрастания.
  2. Количество храмов справа в порядке возрастания.

Наивным методом решения этой проблемы будет для каждого храма: идти налево до увеличения высоты и делать то же самое для правого.

C ++

// Программа для поиска минимального общего количества требуемых предложений
#include <iostream>

using namespace std;

  
// Возвращает минимальные требуемые предложения

int offeringNumber(int n, int templeHeight[])

{

    int sum = 0;  // Инициализировать результат

  

    // Пройдемся по всем храмам один за другим

    for (int i = 0; i < n; ++i)

    {

        // Идем налево, в то время как высота увеличивается

        int left = 0, right = 0;

        for (int j = i - 1; j >= 0; --j)

        {

            if (templeHeight[j] < templeHeight[j + 1])

                ++left;

            else

                break;

        }

  

        // Идем направо, пока высота увеличивается

        for (int j = i + 1; j < n; ++j)

        {

            if (templeHeight[j] < templeHeight[j - 1])

                ++right;

            else

                break;

        }

  

        // Этот храм должен предлагать максимум два

        // значения для следования правилу.

        sum += max(right, left) + 1;

    }

  

    return sum;

}

  
// Код драйвера

int main()

{

    int arr1[3] = {1, 2, 2};

    cout << offeringNumber(3, arr1) << "\n";

    int arr2[6] = {1, 4, 3, 6, 2, 1};

    cout << offeringNumber(6, arr2) << "\n";

    return 0;

}

Джава

// Программа для поиска минимума
// Всего предложений требуется

import java.io.*;

  

class GFG 

{

      
// Возвращает минимум
// предложения требуются

static int offeringNumber(int n, 

                          int templeHeight[])

{

    int sum = 0; // Инициализировать результат

  

    // пройти все

    // храмы один за другим

    for (int i = 0; i < n; ++i)

    {

        // Идем налево, пока

        // высота постоянно увеличивается

        int left = 0, right = 0;

        for (int j = i - 1; j >= 0; --j)

        {

            if (templeHeight[j] < 

                templeHeight[j + 1])

                ++left;

            else

                break;

        }

  

        // Идем направо, пока

        // высота постоянно увеличивается

        for (int j = i + 1; j < n; ++j)

        {

            if (templeHeight[j] < 

                templeHeight[j - 1])

                ++right;

            else

                break;

        }

  

        // Этот храм должен предложить

        // максимум двух значений

        // следовать правилу.

        sum += Math.max(right, left) + 1;

    }

  

    return sum;

}

  
// Код драйвера

public static void main (String[] args) 

{

int arr1[] = {1, 2, 2};

System.out.println(offeringNumber(3, arr1));

int arr2[] = {1, 4, 3, 

              6, 2, 1};

System.out.println(offeringNumber(6, arr2));

}
}

  
// Этот код предоставлен akt_mit

python3

# Программа для поиска минимальной суммы
# предложения необходимы.

  
# Возвращает минимальное необходимое предложение

def offeringNumber(n, templeHeight):

    sum = 0 # Инициализировать результат

      

    # Пройдите все храмы по одному

    for i in range(n):

          

        # Идите налево, пока высота

        # продолжает расти

        left = 0

        right = 0

        for j in range(i - 1, -1, -1):

            if (templeHeight[j] < templeHeight[j + 1]):

                left += 1

            else:

                break

                  

        # Идите направо, пока высота

        # продолжает расти

        for j in range(i + 1, n):

            if (templeHeight[j] < templeHeight[j - 1]):

                right += 1

            else:

                break

                  

        # Этот храм должен предлагать максимум

        # из двух значений, чтобы следовать правилу.

        sum += max(right, left) + 1

    return sum

  
Код водителя

arr1 = [1, 2, 2]

print(offeringNumber(3, arr1)) 

arr2 = [1, 4, 3, 6, 2, 1]

print(offeringNumber(6, arr2)) 

  
# Этот код добавлен
# от sahilshelangia

C #

// Программа для поиска минимума
// Всего предложений требуется

using System;

  

class GFG

{

      
// Возвращает минимум
// предложения требуются

static int offeringNumber(int n, 

                          int []templeHeight)

{

    int sum = 0; // Инициализировать результат

  

    // пройти все

    // храмы один за другим

    for (int i = 0; i < n; ++i)

    {

        // Идем налево, пока

        // высота постоянно увеличивается

        int left = 0, right = 0;

        for (int j = i - 1; j >= 0; --j)

        {

            if (templeHeight[j] < 

                templeHeight[j + 1])

                ++left;

            else

                break;

        }

  

        // Идем направо, пока

        // высота постоянно увеличивается

        for (int j = i + 1; j < n; ++j)

        {

            if (templeHeight[j] < 

                templeHeight[j - 1])

                ++right;

            else

                break;

        }

  

        // Этот храм должен предложить

        // максимум двух значений

        // следовать правилу.

        sum += Math.Max(right, left) + 1;

    }

  

    return sum;

}

  
// Код драйвера

static public void Main ()

{

    int []arr1 = {1, 2, 2};

    Console.WriteLine(offeringNumber(3, arr1));

      

    int []arr2 = {1, 4, 3, 

                  6, 2, 1};

    Console.WriteLine(offeringNumber(6, arr2));

}
}

  
// Этот код предоставлен aj_36

PHP

<?php
// Программа для поиска минимального общего количества требуемых предложений

  
// Возвращает минимальные требуемые предложения

function offeringNumber($n, $templeHeight)

{

    $sum = 0; // Инициализировать результат

  

    // Пройдемся по всем храмам один за другим

    for ($i = 0; $i < $n; ++$i)

    {

        // Идем налево, в то время как высота увеличивается

        $left = 0; $right = 0;

        for ($j = $i - 1; $j >= 0; --$j)

        {

            if ($templeHeight[$j] < $templeHeight[$j + 1])

                ++$left;

            else

                break;

        }

  

        // Идем направо, пока высота увеличивается

        for ($j = $i + 1; $j < $n; ++$j)

        {

            if ($templeHeight[$j] < $templeHeight[$j - 1])

                ++$right;

            else

                break;

        }

  

        // Этот храм должен предлагать максимум два

        // значения для следования правилу.

        $sum += max($right, $left) + 1;

    }

  

    return $sum;

}

  
// Код драйвера

    $arr1 = array (1, 2, 2);

    echo offeringNumber(3, $arr1) , "\n";

    $arr2 = array (1, 4, 3, 6, 2, 1);

    echo offeringNumber(6, $arr2) ,"\n";

      
// Этот код предоставлен ajit
?>


Выход:

4
10

Временная сложность: O (n 2 )
Пространство сложность: O (1)

Подход динамического программирования
Используя динамическое программирование, мы можем улучшить сложность времени. В этом методе мы создаем структуру длины n, которая поддерживает максимальную убывающую цепь слева от каждого храма и максимальную убывающую цепь справа от каждого храма. Проходим один раз от 0 до N, устанавливая значение left для каждого храма. Затем мы идем от N до 0, устанавливая значение права для каждого храма. Затем мы сравниваем два и выбираем максимум для каждого храма.

C ++

// Программа для поиска требуемых предложений
#include <iostream>

using namespace std;

  
// Хранить количество храмов возрастающего порядка
// слева и справа (включая текущий храм)

struct Temple

{

    int L;

    int R;

};

  
// Возвращает количество минимальных предложений для
// n храмов данной высоты.

int offeringNumber(int n, int templeHeight[])

{

    // Инициализировать счетчики для всех храмов

    Temple chainSize[n];

    for (int i = 0; i < n; ++i)

    {

        chainSize[i].L = -1;

        chainSize[i].R = -1;

    }

  

    // Значения угловых храмов

    chainSize[0].L = 1;

    chainSize[n-1].R = 1;

  

    // Заполняем левые и правые значения одинаково

    // значения предыдущего (или следующего)

    for (int i=1; i<n; ++i)

    {

        if (templeHeight[i - 1] < templeHeight[i])

            chainSize[i].L = chainSize[i - 1].L + 1;

        else

            chainSize[i].L = 1;

    }

    for (int i=n-2; i>=0; --i)

    {

        if (templeHeight[i + 1] < templeHeight[i])

            chainSize[i].R = chainSize[i + 1].R + 1;

        else

            chainSize[i].R = 1;

    }

  

    // Вычисляем максимум левого и правого для всех

    // храмы и возвращающие суммы.

    int sum = 0;

    for (int i = 0; i < n; ++i)

        sum += max(chainSize[i].L, chainSize[i].R);

    return sum;

}

  
// Функция драйвера

int main()

{

    int arr1[3] = {1, 2, 2};

    cout << offeringNumber(3, arr1) << "\n";

    int arr2[6] = {1, 4, 3, 6, 2, 1};

    cout << offeringNumber(6, arr2) << "\n";

    return 0;

}


Выход:

4
10

Временная сложность: O (n)
Пространственная сложность: O (n)

Эта статья предоставлена Адитьей Каматом . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Предложения храма

0.00 (0%) 0 votes