Я занимаюсь соревновательным кодированием несколько месяцев. В настоящее время я решаю проблемы SPOJ.

Сегодня я столкнулся с интересной задачей под названием СМЕСИ. В основном в постановке задачи говорится, что

Имеются n смесей, расположенных в ряд. Каждая смесь имеет один из 100 различных цветов (цвета имеют номера от 0 до 99). Нужно смешать все эти смеси вместе. На каждом шаге мы можем взять две смеси, стоящие рядом, и смешать их между собой, а полученную смесь поставить на их место. При смешивании двух смесей цветов а и b полученная смесь будет иметь цвет (а+b ) мод 100.

Кроме того, в процессе будет немного дыма. Количество дыма, образующегося при смешивании двух смесей цветов a и b, равно a*b. Выясните, какое минимальное количество дыма может получиться при смешивании всех смесей вместе.

После прочтения условия задачи стало очевидно, что это проблема динамического программирования. Я пытался решить это в течение часа, но не нашел ответа.

Умножение цепочки матриц является ключом к решению этой проблемы. Я настоятельно рекомендую сначала изучить MCM.

Теперь, переходя к этой проблеме, мы видим, что здесь есть перекрывающиеся подзадачи. Предположим, есть 3 числа 40,60 и 20.

мы можем найти ответ разными способами

((40*60)*20) = 0*20 = 20. Дым = 2400 + 0 = 2400.

(40*(60*20)) = 40*80 = 20. Дым = 1200 + 3200 = 4400.

Ясно, что второй способ лучше.

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

Назовем оба массива как sum[][] и dp[][], а array[] — входной массив.

Заполнение матрицы суммы

sum[i][j] = сумма входных чисел от индекса i до индекса j.

мы можем ясно сказать, что sum[i][i] = array[i]

Матрица может быть заполнена по этой формуле

сумма[i][j] = (сумма[i][j-1] + обр[j])%100; (нам нужно заполнить только ячейки выше диагонали матрицы суммы)

for(int i=0;i‹n;i++)
{
sum[i][i] = arr[i];
for(int j=i+1;j‹ n;j++)
sum[i][j] = (sum[i][j-1] + arr[j])%100;
}

Теперь нам нужно найти минимальный дым среди всех возможных ответов.

Давайте пойдем вдоль, я имею в виду, что мы сначала рассмотрим подзадачи длины 1, затем длины 2 и так далее…

Возьмем 4 числа 10,20,30 и 40.

Длина 0:

результат = 0, так как нам нужно как минимум два числа для умножения, правильно.

so dp[i][i] = 0

Длина 2:

возможные комбинации: 10–20, 20–30 и 30–40.

для 10–20 результирующая смесь = (10 + 20)% 100 = 30 и дым = 200.

для 20–30 результирующая смесь = (20 + 30)% 100 = 50 и дым = 600.

для 30–40 результирующая смесь = (30 + 40)% 100 = 70 и дым = 1200.

Длина 3:

возможные комбинации: 10–20–30, 20–30–40.

для 10–20–30 у нас есть две возможности: (10 (20 30)) или ((10 20) 30). мы возьмем минимум обоих. Интересно, что мы можем найти решение этой длины, используя предыдущее решение длины.

Длина 4:

возможные комбинации 10–20–30–40.

аналогично мы можем сделать (10 (20 30 40)) или ((10 20) (30 40)) или ((10 20 30) 40).

код для приведенного выше объяснения:

for(ll i=n-1; i›=0; i — )
{
dp[i][i] = 0;

for(ll j=i+1; j‹n; j++)
{
dp[i][j] = INT_MAX;
for(ll k=i;k‹j;k++ )
{
ll val = dp[i][k] + dp[k+1][j] + (sum[i][k]*sum[k+1][j]) ;
dp[i][j] = min(dp[i][j], val);
}
}
}

окончательный результат можно найти по адресу dp[0][n-1].

Удачного кодирования :)