Матч 21, Избирательная система (ElectiveSystem)

Студенты Байтляндского университета для занятий используют автоматическую систему регистрации. Регистрация открыта определенный период времени. При этом каждый момент времени имеет характеристику, которая описывается положительным числом. Входить в систему можно не более k раз, каждый вход может длиться не более d единиц времени. Периоды нахождения в системе не должны пересекаться.

Имеется массив values. Его строки следует объединить в одну большую строку. i - ый символ полученной строки описывает характеристику в i - ый момент времени. Характеристика задается буквами от ‘a’ до ‘z’, обозначающих соответственно числа от 1 до 26. Необходимо разработать стратегию, для которой сумма характеристик периодов времен нахождения в системе наибольшая.

Класс: ElectiveSystem

Метод: int maximalGoodness(vector<string> values, int d, int k)

Ограничения: values содержит от 1 до 20 строк, каждая из которых не пустая и состоит из не более 50 букв ‘a’ – ‘z’, 1 £ d, k £ 1000.

Вход. Массив строк values, целые числа d и k.

Выход. Наибольшая возможная сумма характеристик.

Пример входа

values	d	k
{"acacca"}	4	1
{"cab","cca"}	2	2
{"yptcsevnuzlsrfjxurpslztlinhddelpitmvaezowjcfjjfgmf","q"}	2	18

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

10

10

598

РЕШЕНИЕ

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

В ячейках s[i] будем хранить сумму характеристик всех моментов времени от 1 до i - го. В d[i][j] будет находиться наибольшая возможная сумма характеристик периодов времен при условии, что уже прошло i единиц времени, а в систему входили в точности j раз. Тогда имеет место соотношение:

dp[i][j] = max{dp[i – d][j – 1] + s[i] – s[i – d], dp[i – 1][j]}

При этом значение i – d считается равным нулю, если i – d < 0. Из уравнения следует, что:

1. Если в i - ый момент времени студент не находится в системе, то dp[i][j] = dp[i – 1][j].

2. Поскольку значения всех характеристик положительны, то чем больше мы будем в системе, тем большей будет сумма характеристик. Если в i - ый момент времени студент находится в системе, то считаем, что вошел он туда в (i – d + 1) - ый момент времени. В этом случае dp[i][j] = dp[i – d][j – 1] + s[i] – s[i – d]. Заметим, что разница s[i] – s[i – d] равна сумме характеристик с (i – d + 1) - го по i - ый момент времени. Например, при d = 2, i = 5 s[5] – s[3] содержит сумму характеристик для 4 и 5 момента времени.

ПРОГРАММА

#include <cstdio>

#include <string>

#include <vector>

#include <numeric>

using namespace std;

int s[1001],dp[1001][1001];

class ElectiveSystem

{

public:

int maximalGoodness(vector<string> values, int d, int k)

{

int i, j, temp;

string str = accumulate(values.begin(),values.end(),string());

memset(s,0,sizeof(s));

for(i = 1; i <= str.size(); i++) s[i] = s[i-1] + str[i-1] - 'a' + 1;

memset(dp,0,sizeof(dp));

for(i = 1; i <= str.size(); i++)

for(j = 1; j <= k; j++)

{

temp = (i - d) < 0 ? 0 : i - d;

dp[i][j] = max(dp[i-1][j],dp[temp][j-1] + s[i] - s[temp]);

}

return dp[str.size()][k];

}

};