Минимизация затрат на обход массивов с заданной стоимостью переключения массивов

Опубликовано: 19 Сентября, 2022

Учитывая три массива A[] , B[] и C[] размера N каждый и два целых числа X и Y , задача состоит в том, чтобы найти минимальную стоимость достижения конца массивов со следующими условиями:

  • Выберите один из трех элементов в каждом индексе.
  • Для переключения с 1-го массива на 2-й или наоборот требуются дополнительные Х точек и
  • Для переключения со 2-го массива на 3-й или наоборот требуются дополнительные точки Y.
  • Первый элемент (с индексом 0) должен быть выбран только из 1-го массива.

Примечание. Невозможно напрямую переключиться с 1-го на 3-й массив или наоборот.

Примеры:

Input:  X = 6, Y = 3
A[] = { 30, 10, 40, 2, 30, 30 }
B[] = { 10, -5, 10, 50, 7,  18 }
C[] = { 4, 20, 7, 23, 2, 10 }
Output: 75
Explanation: We select this elements at index (0 to N-1). 
A[] = { 30, 10, 40, 2, 30, 30 }
B[] = { 10, -5, 10, 50, 7,  18 }
C[] = { 4, 20, 7, 23, 2, 10 }
From index 0 we have to select 30. So Total cost to traverse up to index 0 is 30.
Now At index 1, 3 options (10, -5, 20). So select -5 from 2nd array.
So extra X (X = 6) cost required to shift from 1st array to 2nd. 
So Total cost to traverse up to index 1 is 30 + 6 – 5 = 31.
At index 2, select 10. So Total cost to traverse upto index 2 is 31+10= 41.
At index 3, select 2 from 1st array,  
So extra X (X = 6) points required to shift from 2nd array to 1st. 
So Total cost to traverse upto index 3 is 41+6+2 = 49 and so on.
So, total cost = 30 + (6+(-5)) + 10 + (6+2) + (6+7) + (3+10) = 75
6 and 3 are the extra costs required to change array.

Input:  X = -5, Y = 4
A[] = { 30, 10, -15, 10, 50, 7 }
B[] = { 4, 20, 7, 23, 2, 18 }
C[] = { 30, 10, 40, 2, 30, 10 }
Output: 34

Подход: проблема может быть решена на основе жадного подхода, основанного на следующей идее:

At each index try to include the element from the array that will include the minimum cost. And also keep in mind that we can go from A[] to B[], B[] to C[], B[] to A[] and C[] to B[] not from A[] to C[] or C[] to A[]. 

Для реализации идеи выполните следующие шаги:

  • Создайте двумерный массив (например, min_pnts [N][3]).
  • Пройдите массив от последнего индекса к первому индексу и на каждой итерации:
    • Значение min_pnts[i][0] зависит от min_pnts[i+1][0] и min_pnts[i+1][1] , значение min_pnts[i][1] зависит от min_pnts[i+1][ 1], min_pnts[i+1][0] и min_pnts[i+1][2] , значение min_pnts[i][2] зависит от min_pnts[i+1][2] и min_pnts[i+1] [1] .
    • Проверьте, какой путь требует минимального количества точек (т.е. с коммутационной матрицей или без).
    • Сохраните минимальное количество баллов, необходимое, если мы выберем текущий элемент индекса из 1-го, 2-го или 3-го массива.
  • Возвращает минимальное количество точек, необходимых для обхода массива.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N)
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ