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

жүктеу/скачать 0.53 Mb.

бет	6/6
Дата	19.07.2016
өлшемі	0.53 Mb.
	#208895
түрі	Решение

1 2 3 4 5 6

15. Забор для травы [Топкодер, раунд 314, дивизион 2, уровень 3; дивизион 1, уровень 2]. Площадь треугольника со сторонами a, b, c ищем в функции area(a, b, c) по формуле Герона:

S = , где p =

Пусть P – некоторое подмножество имеющихся кусков забора. Функция FindSol(mask) будет находить максимальную площадь, которую можно оградить при помощи них треугольными формами. Переменная mask содержит маску подмножества: она является 16-битовым числом, i-ый бит которого равен 1, если подмножество P содержит кусок fences[i], и 0 иначе. Ответом на задачу в таком случае будет значение FindSol(2ⁿ - 1), где n – количество чисел в массиве fences.

Значения всевозможных масок mask лежит в промежутке от 0 до 2¹⁶ – 1 (по условию имеются не более 16 кусков забора). В ячейке best[mask] храним максимальную площадь, которую можно оградить подмножеством кусков изгороди, описывающим маской mask.

Для вычисления FindSol(mask) следует перебрать все возможные тройки кусков забора i, j, k, присутствующих в mask, проверить для них неравенство треугольника (можно ли из них составить треугольник) и найти сумму area(fences[i], fences[j], fences[k]) + FindSol(mask \ {i, j, k}). Перебираем все тройки (i, j, k) и находим такую, для которой указанная сумма максимальна. Ее значение присваиваем ячейке best[mask]. Извлечение из подмножеста mask i – го элемента эквивалентно выполнению операции исключающего или: mask ^ (1 << i).

Если изначально длины кусков забора отсортировать, то при проверке неравенства треугольника (стороны которого равны fences[i], fences[j], fences[k]), достаточно проверить только одно условие:

fences[i] + fences[j] > fences[k],

так как из неравенства fences[i]  fences[j]  fences[k] всегда сдедует, что fences[i] + fences[k] > fences[j] и fences[j] + fences[k] > fences[i].
#include

#include

using namespace std;
double best[1<<16];

int n;
class GrasslandFencer{

public:

vector f;

double FindSol(int mask)

{

int i,j,k;

double mx = 0;

if (best[mask] >= 0.0) return best[mask];

if (!mask) return 0;

for(i=0;i

for(j=i+1;j

for(k=j+1;k

if (f[i] + f[j] > f[k]) mx = max(mx,area(f[i],f[j], f[k])+

FindSol(mask ^ (1 << i) ^ (1 << j) ^ (1 << k)));

best[mask] = mx;

return mx;

}
double area(int a, int b, int c)

{

double p = (a+b+c)/2.0;

return sqrt(p*(p-a)*(p-b)*(p-c));

}
double maximalFencedArea(vector fences)

{

sort(fences.begin(),fences.end());

n = fences.size(); f = fences;

memset(best,-1,sizeof(best));

return FindSol((1<

}

};

16. Починка забора [Топкодер, раунд 325, дивизион 1, уровень 1]. Исходя из ограничений на массив 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

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

using namespace std;
class FenceRepairing

{

public:

double calculateCost(vector 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()];

}

};
17. Расширенное счастливое число [Топкодер, раунд 334, дивизион 2, уровень 3; дивизион 1, уровень 2]. Поскольку значение k в процессе вычислений фиксировано, заведем массив powk, в котором powk[i] = i^k. Им будет удобно пользоваться при вычислении значений S_k(n) в функции sum(n). Наибольшее значение, которое могут принимать элементы последовательности n, S_k(n), S_k(S_k(n)), …, не больше 4*10⁶, так как даже при k = 6 значение S₆(n) при n < 4*10⁶ не больше 3⁶ + 6*9⁶ = 3189375 < 4*10⁶.

Заведем массив f[4000000], в котором будем хранить f[i] = S_k(i). Рассмотрим для некоторого i последовательность a₀ = i, a₁ = S_k(i), a₂ = S_k(S_k(n)), … . Очевидно, что найдутся такие индексы s и t (пусть s < t для определенности), что a_s = a_t. Тогда f[a_k], (0  k  t) положим равным минимуму среди чисел a_k, a_k₊₁, …, a_t. При этом начиная вычислять значение f[a₀], в процессе мы находим все значения f[a_k], 0  k  t.

Описанную процедуру совершаем в функции g. Значение f[i] считается вычисленным, если f[i] > 0. При первом проходе по числам a₀, …, a_t устанавливаем f[a_i] = -1. Дойдя до a_t = a_s, продолжаем путь a_s , a_s₊₁, …, a_t, устанавливая f[a_i] = a_i для s  i  t. Когда вторично дойдем до f[a_t], значение этой ячейки уже будет положительным и рекурсия начнет раскручиваться назад. Двигаясь назад по кольцу дважды от a_t до a_s, а потом и до a₀, устанавливаем f[a_i] в наименьшее значение среди чисел a_i, a_i₊₁, …, a_t.

#include

#define i64 long long

#define MAX 4000000
int powk[10];

int f[MAX],ptr;

int min(int i, int j)

{

return (i < j) ? i : j;

}
int sum(int n)

{

int s;

for(s=0;n;n/=10)

s += powk[n % 10];

return s;

}
int g(int n)

{

if (f[n] > 0) return f[n]; else

if (f[n] == 0) f[n] = -1; else

if (f[n] == -1) f[n] = n;

return f[n] = min(n,g(sum(n)));

}
class ExtendedHappyNumbers

{

public:

i64 calcTheSum(int a, int b, int k)

{

int i,j,s;

i64 res=0;

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

{

for(s=1,j=0;j

powk[i] = s;

}

for(i=a;i<=b;i++)

res += g(i);

return res;

}

};
18. Быстрый почтальон [Топкодер, раунд 346, дивизион 2, уровень 3]. Если почтальон на своем пути поравняется с некоторым домом, куда следует доставить письмо, то его следует отдавать сразу же, при первом же подходе к дому. Если почтальон уже разнес письма в i - ый и j - ый дома, то он точно уже разнес письма во все дома, которые находятся между i - ым и j - ым домом. Таким образом, множество домов, куда уже разнесена почта, представляет собой отрезок прямой с точкой initialPos внутри. Следует также отметить, что направление движения почтальон может менять только в точке с домом, в который он только что доставил письмо.

Состояние почтальона определим тройкой чисел:

1. левый конец интервала домов, куда уже разнесена почта;

2. правый конец интервала домов, куда уже разнесена почта;

3. текущее положение почтальона;

Вместо самих чисел в состоянии почтальона лучше хранить их индексы в массиве address. На каждом шаге (i, j, k) следует определить, куда лучше двигаться почтальону: вправо (i, j + 1, j + 1) или влево (i – 1, j, i – 1). Также заметим, что для каждого состояния (i, j, k) текущее положение почтальона k равно i или j.

В ячейках sol[i][j][0] будем хранить наименьшее время, за которое почтальон разнесет все письма в дома в интервале (i, j), причем находиться будет в точке i (в левом конце интервала). Соответственно в sol[i][j][1] будет содержаться та же информация, только почтальон будет находиться в правом конце интервала – в точке j.

Отсортируем адреса домов по возрастанию их координат. Чтобы при сортировке соответствующим образом переставлялось и граничное время доставки, создадим вектор пар houses, первый элемент которого содержит адрес дома, а второй – максимальное время доставки письма в этот дом. При сортировке вектора пар по возрастанию сортировка производится по первой компоненте – то есть по расстоянию от левого края улицы.

Инициализация массива sol:

sol[i][i][0] = sol[i][i][1] = | address[i] – initialPos | = | houses[i].first – initialPos |

Для доставки письма в единственный дом, индекс которого равен i, необходимо затратить время, равное расстоянию от начального положения initialPos до местоположения дома address[i].

Рассмотрим интервал (i, j). Почтальон может оказаться в его левом конце двигаясь либо с левого конца интервала (i + 1, j), либо с правого конца интервала (i + 1, j). В первом случае ему требуется пройти расстояние address[i + 1] – address[i], во втором address[j] – address[i]. То есть

sol[i][j][0] =

= min(sol[i + 1][j][0] + address[i + 1] – address[i], sol[i + 1][j][1] + address[j] – address[i])

Аналогично почтальон может оказаться в правом конце итервала (i, j), если он будет двигаться либо с левого конца интервала (i, j – 1), либо с правого конца интервала (i, j – 1). В первом случае ему требуется пройти расстояние address[j] – address[i], во втором address[j] – address[j – 1]. Таким образом

sol[i][j][1] =

= min(sol[i][ j – 1][0] + address[j] – address[i], sol[i][ j – 1][1] + address[j] – address[j – 1])

Если на каком-нибудь этапе вычисления значение sol[i][j][0] (или sol[i][j][1]) станет большим maxTime[i] (или соответственно maxTime[j]), то установим его равным плюс бесконечности (значению INF = 2000000000). Последнее означает тот факт, что добраться до соответствующего дома в отведенное время почтальон не может.

Почтальон доставит все письма, когда будут пройдены все дома из интервала (0, n – 1), где n – количество домов. При этом нам не важно, в каком из концов этого интервала закончит путь почтальон. То есть ответом будет значение

min(sol[0][n – 1 ][0], sol[0][n – 1][1])

Если это значение равно плюс бесконечности, то разнести письма в срок не удастся и следует вернуть -1 как требуется в условии задачи.

#include

#define INF 2000000000

using namespace std;

int sol[50][50][2];
int min(int i, int j)

{

return (i < j) ? i : j;

}
class FastPostman

{

public:

int minTime(vector address, vector maxTime, int initialPos)

{

int res,i,j,n = address.size();

vector
> houses;

for(i=0;i

sort(houses.begin(),houses.end());

memset(sol,0,sizeof(sol));

for(i=0;i

{

sol[i][i][0] = sol[i][i][1] = abs(houses[i].first - initialPos);

if (sol[i][i][0] > houses[i].second) sol[i][i][0] = sol[i][i][1] = INF;

}

for(i=n-1;i>=0;i--)

{

for(j=i+1;j

{

sol[i][j][0] = min(sol[i+1][j][0]+houses[i+1].first-houses[i].first,

sol[i+1][j][1]+houses[j].first-houses[i].first);

if (sol[i][j][0] > houses[i].second) sol[i][j][0] = INF;

sol[i][j][1] = min(sol[i][j-1][0]+houses[j].first-houses[i].first,

sol[i][j-1][1]+houses[j].first-houses[j-1].first);

if (sol[i][j][1] > houses[j].second) sol[i][j][1] = INF;

}

res = min(sol[0][n-1][0],sol[0][n-1][1]);

if (res == INF) return -1;

return res;

}

};

19. Прыгатель по платформам [Топкодер, раунд 353, дивизион 2, уровень 3; дивизион 1, уровень 2]. Поскольку игрок при прыжках всегда движется вниз, то его путь всегда конечный, а каждая платформа может быть посещена не более одного раза. Пусть opt[i] содержит наибольшее количество монет, которое можно собрать по всем путям, заканчивающихся на i - ой платформе. Обозначим через s[i] множество платформ, с каждой из которых за один прыжок можно попасть на i - ую платформу. Пусть coins[i] – количество монет, находящихся на i - ой платформе. Тогда имеет место рекуррентность:

opt[i] = coins[i] +

Остается научиться определять, можно ли прыгнуть из одной платформы на другую. Пусть платформы имеют координаты (x₁, y₁) и (x₂, y₂), y₁ > y₂. Игрок должен преодолеть по горизонтали расстояние |x₁ – x₂|, по вертикали |y₁ – y₂|. Наибольшая горизонтальная скорость движения при прыжке равна v, которая по условию задачи постоянна. Тогда время, за которое может быть преодолена горизонтальная составляющая, равно t = |x₁ – x₂| / v. Вычислим расстояние, на которое переместится за это время игрок по оси ординат. Оно равно

dy = g * t² / 2

Если dy > |y₁ – y₂|, то прыжок совершить невозможно. Перепишем последнее неравенство в виде:

g * |x₁ – x₂|² / 2v² > |y₁ – y₂|,

или для избежания операции деления:

g * |x₁ – x₂|² > |y₁ – y₂| * 2v²

Отсортируем платформы по y - координате. Последовательно, начиная с наивысшей платформы, вычисляем значения массива opt согласно выше приведенной рекуррентной формуле. В переменной res накапливаем ответ – он равен наибольшему значений среди всех ячеек массива opt.

#include

#define i64 long long

using namespace std;

struct pos

{

i64 x,y,coins;

} c[50];
int f(pos a, pos b)

{

return a.y < b.y;

}
class PlatformJumper

{

public:

int maxCoins(vector platforms, int v, int g)

{

int i,j,res,n=platforms.size(),opt[50];

for(res=i=0;i

sscanf(platforms[i].c_str(),"%lld %lld %lld",

&c[i].x,&c[i].y,&c[i].coins);

sort(c,c+n,f);

for(i=n-1;i>=0;i--)

{

opt[i] = c[i].coins;

for(j=i+1;j

if ((opt[j] + c[i].coins > opt[i]) &&

(g*(c[i].x - c[j].x)*(c[i].x - c[j].x) <= (c[j].y - c[i].y)*2*v*v))

opt[i] = opt[j] + c[i].coins;

if (opt[i] > res) res = opt[i];

}

return res;

}

};

СПИСОК ИСПОЛЬЗОВАННЫХ ЗАДАЧ

[Вальядолид] acm.uva.es/problemset:

147, 357, 674 (Доллары), 348 (Оптимальное умножение матриц), 10405 (Наибольшая общая подпоследовательность), 10681 (Путешествие Теобальдо), 10702 (Путешествующий торговец), 10767 (Трамваи в Барселоне), 10910 (Распределение оценок), 10943 (Как Вы прибавляете?), 11026 (Задача группирования).

[Топкодер] www.topcoder.com:

SRM 298 (Подсчет общих подпоследовательностей), SRM 301 (Исправить расстановку скобок), SRM 311 (Просуммировать всех), SRM 314 (Забор для травы), SRM 325 (Починка забора), SRM 334 (Расширенное счастливое число), SRM 346 (Быстрый почтальон), SRM 353 (Прыгатель по платформам).

жүктеу/скачать 0.53 Mb.

Достарыңызбен бөлісу:

1 2 3 4 5 6