Матч 325, Починка забора (FenceRepairing)

Дивизион 1, Уровень 1

Вам необходимо починить старый забор. Забор состоит из набора досок, некоторые из которых выломаны. Доски пронумерованы слева направо в возрастающем порядке. Починка всех досок от i - ой до j - ой (i < j) стоит . Целые доски обозначаются символом ‘.’ (точка), сломанные – ‘X’. Для уменьшения общей стоимости ремонта иногда выгодно ремонтировать даже целые доски. Необходимо найти минимальную стоимость ремонта всего забора.

Класс: FenceRepairing

Метод: double calculateCost(vector<string> boards)

Ограничения: boards содержит от 1 до 50 элементов, boards[i] содержит от 1 до 50 символов ‘.’ И ‘X’.

Вход. Массив строк boards. Объединив их, получим состояние забора, который подлежит ремонту.

Выход. Минимальная стоимость ремонта всего забора.

Пример входа

boards

{"X.X...X.X"}

{"X.X.....X"}

{".X.......X", "..........", "...X......", "...X..X...", "..........",

"..........", "..X....XX.", ".........X", "XXX", ".XXX.....X"}

Пример выхода

3.0

2.732050807568877

9.591663046625438

РЕШЕНИЕ

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

Исходя из ограничений на массив boards и на длины его элементов, заключаем, что длина наибольшего возможного входного забора не более 50*50 = 2500. Объединим строки массива boards в b. Заведем массив c длины 2501, в котором c[i] будет хранить минимальную стоимость, за которую можно починить забор от нулевой позиции до (i – 1) - ой, причем c[0] положим равным 0. Тогда дешевле всего починить первые i секции (от 0 - ой до (i – 1) - ой) забора следующим образом:

1. Если i - ая секция цела (b[i – 1] = ‘.’), то достаточно починить только первые i – 1 секций: c[i] = c[i – 1];

2. Если i - ая секция сломана (b[i – 1] = ‘X’), то чиним забор от 0 - ой до j - ой секции (0 £ j < i), потратив c[j] денег, а затем чиним доски от (j + 1) - ой до i - ой секции за денег. При этом среди всех возможных j следует выбрать такое, для которого сумма c[j] + наименьшая.

Положив c[0] = 0, последовательно вычисляем c[1], c[2] , …, c[n], где n – длина забора. Ответом задачи будет значение c[n].

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

#include <cmath>

#include <numeric>

#define min(i,j) (i < j) ? i : j

using namespace std;

class FenceRepairing

{

public:

double calculateCost(vector<string> boards)

{

string b = accumulate(boards.begin(),boards.end(),string());

int i, j;

double c[2501];

for(c[0] = 0, i = 1; i <= b.size(); i++)

{

c[i] = 2000000000;

if (b[i-1] == '.') c[i] = c[i-1]; else

for(j = 0; j < i; j++)

c[i] = min(c[i],c[j] + sqrt(1.0 * i - j));

}

return c[b.size()];

}

};