Отримання знань
дистанційна підтримка освіти школярів
N гангстеров собираються в ресторан. i-ый гангстер приходит в момент времени Ti, богатство этого гангстера - Pi. Дверь ресторана имеет K+1 степень открытости, они обозначаются целыми числами из интервала [0, K]. Степень открытости дверей может изменяться за единицу времени, т.е. дверь может открыться на единицу, закрыться на единицу или остаться в том же положении, в котором была. В начальный момент времени дверь закрыта (положение 0). i-й гангстер заходит в ресторан, только если дверь открыта специально для него, т.е. степень открытости двери соответствует его полноте Si. Если в момент, когда гангстер подходит к ресторану, степень открытости не соответствует его полноте, он уходит и больше не возвращается. Ресторан работает в интервале времени [0, T]. Требуется собрать гангстеров с максимальным суммарным капиталом в ресторане, открывая и закрывая дверь соответствующим образом.
Входные данные
В первой строке входных данных содержаться значения N, K и T, разделенные пробелом:
(1 <= N <= 100 , 1 <= K <= 100, 0 <= T <= 30000 ).
Во второй строке входных данных задано время приезда каждого гангстера в ресторан T1, T2 ..., TN, разделенные пробелом. (0 <= Ti <= T).
Третья строка входных данных содержит капитал каждого гангстера P1, P2, ..., PN, разделенных пробелами. (0 <= Pi <= 300).
Следующая (четвертая) строка входных данных содержит полноту каждого гангстера S1, S2, ..., SN, разделенных пробелом (1 <= Si <= K).
Все входные данные - целые числа.
Выходные данные
Вывести единственное число - максимальный собранный суммарный капитал
Пример входных данных
4 10 20
10 16 8 16
10 11 15 1
10 7 1 8
Пример выходных данных
26
Анализ условия и обсуждение идеи решения
Детальный разбор приведен в книге Ф.Меньшикова "Олимпиадные задачи по программированию", М., 2006. Собственно мы его и приведем, с некоторыми комментариями и уточнениями.
Решение, предложенное Александром Меркуловым, метод решения - динамическое программирование
Отсортируем гангстеров по неубыванию времени прихода. Если полнота гангстера больше его времени прихода, то он не может попасть в ресторан. Богатство такого гангстера устанавливаем равным 0 - в этом случае от того, зашел он или нет, конечный результат не зависит.
Рассматриваем гангстеров в порядке неубывания времени прихода, и для каждого вычисляем, каким получиться суммарное богатство, если этот гангстер станет последним пришедшим. Ничего не стоит найти эту характеристику, если известны характеристики гангстеров, пришедших раньше (они уже рассмотрены). Если только один этот гангстер попал в ресторан, то суммарное богатство будет равно его богатству. В противном случае перебираем, какой из уже рассмотренных к данному моменту гангстеров был предпоследним. Если в ресторан попало более одного гангстера, суммарное богатство буде равно суммарному богатству (характеристике) предпоследнего гангстера плюс богатство последнего. Конечно, не любой гангстер может быть предпоследним - должно выполняться следующее неравенство: модуль разности полноты должен не превосходить разности времени прихода. Выбирая максимум характеристик претендентов, получаем значение характеристики для текущего гангстера.
Какой-то из гангстеров является последним в оптимальном плане открытия дверей. Нужно просто найти максимум из полученных характеристик.
Второй вариант решения также базируется на методе динамического программирования.
Исключим из входных данных гангстеров, у которых полнота больше времен прихода.
Заполняем таблицу M[0..30100, 0..100] - первый индекс означает текущее время, второй - текущую степень открытости дверей. Элемент таблицы M[t,i] означает, что к моменту времени t, если дверь оказалась в состоянии i, суммарное богатство может составить M[t, i]. Ответом задачи будет являться число число M[30100, 0] - даже если последний гангстер имел полноту 100 и пришел в момент времени 30000, все равно к моменту времени 30100 можно считать, что дверь закрыта.
Итак, заполняем таблицу. Для M[0, i], 0 <= i <= 100, значение таблицы 0. Гангстеров полноты 0 не существует, а остальные не могли попасть в нулевой момент времени.
Пусть для фиксированного t известны все M[t-1, i], 0 <= i <= 100. Найдем все M[t, i]. В состояние i в момент времени t можно попасть только из состояний i, i-1 или i+1 в момент времени t-1. Значит, выбираем из них оптимальное M[t, i] = max(M[t-1, i-1], M[t-1, i+1]). Также добавим к M[t, i] богатство гангстеров, приходящих в момент времени t и имеющих полноту i, - если уж дверь открыта специально для них, то почему бы им не войти?
Когда таблица заполнена, осталось только вывести результат - M[30100, 0].
В предложенном ниже варианте реализации мы не используем такой большой массив, как описано в разборе Ф. Меньшикова - нам достаточно массива a[2][101]. С деталями реализации предлагается разобраться самостоятельно.
Пример решения на С++:
#include < iostream >using namespace std;
int main()
{
int n,k,time,i,j,max,ii,temp;
int t[100],p[100],s[100],a[2][101];
cin >> n >> k >> time;
for(i=0; i < n; i++)
cin >> t[i];
for(i=0; i < n; i++)
cin >> p[i];
for(i=0; i < n; i++)
cin >> s[i];
for(j=0; j <= k; j++)
{
a[0][j]=0;
}
for(i=0; i < n-1; i++)
for(j=i+1; j < n; j++)
if (t[i] > t[j])
{
temp=t[i];
t[i]=t[j];
t[j]=temp;
temp=s[i];
s[i]=s[j];
s[j]=temp;
temp=p[i];
p[i]=p[j];
p[j]=temp;
}
ii=1;temp=0;
while (t[temp]==0)
temp++;
for(i=1; i <= time && temp < n; i++)
{
for(j=0; j <= k; j++)
{
a[ii][j]=0;
if (j > 0 && a[1-ii][j-1] > a[ii][j]) a[ii][j]=a[1-ii][j-1];
if (a[1-ii][j] > a[ii][j]) a[ii][j]=a[1-ii][j];
if (j < k && a[1-ii][j+1] > a[ii][j]) a[ii][j]=a[1-ii][j+1];
}
while (temp<n&&t[temp]==i)
{
if(s[temp] <= i)
a[ii][s[temp]]+=p[temp];
temp++;
}
ii=1-ii;
}
max=0;
for(i=0; i <= k;i++)
if(max < a[1-ii][i]) max = a[1-ii][i];
cout << max << endl;
}
| Попередня | Зміст | Наступна |