Решение задачи "Гангстеры" с Меньшиков

Без пояснения   Просмотров: 37

N гангстеров собираются в ресторан. i-й гангстер приходит в момент времени Ti и имеет богатство Pi. Дверь ресторана имеет K + 1 степень открытости, они обозначаются целыми числами из интервала [0, K]. Степень открытости двери может изменяться на единицу в единицу времени, то есть дверь может открыться на единицу, закрыться на единицу или остаться в том же состоянии. В начальный момент времени дверь закрыта (степень открытости 0). i-й гангстер заходит в ресторан, только если дверь открыта специально для него, то есть когда степень открытости двери соответствует его полноте Si. Если в момент, когда гангстер подходит к ресторану, степень открытости двери не соответствует его полноте, он уходит и больше не возвращается. Ресторан работает в интервале времени [0, T]. Требуется собрать гангстеров с максимальным суммарным богатством в ресторане, открывая и закрывая дверь соответствующим образом.

Код 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> t,p,s;
vector<int> maxP;
int n,k,tt;
void input(){
    cin>>n>>k>>tt;
    t.resize(n); p.resize(n); s.resize(n); maxP.resize(n);
    for (int i=0;i<n;i++) cin>>t[i]; // время
    for (int i=0;i<n;i++) cin>>p[i]; // кошелек
    for (int i=0;i<n;i++) cin>>s[i]; // полнота
    for (int i=0;i<n;i++)
        if (t[i]<s[i]) p[i] = 0; // ганстер вообще не сможет войти в магазин
}
void sortT()
{
    // O(n*n) - сортировка выбором
    for (int i=0;i<n;i++)
        for (int j=i+1;j<n;j++)
        {
            if (t[i]>t[j])
            {
                swap(t[i],t[j]);
                swap(p[i],p[j]);
                swap(s[i],s[j]);
            }
        }
}
void solve()
{
    sortT();
    for (int i=0;i<n;i++)
    {
        int curMaxPayment = p[i]; // i-ый гангстер по умолчанию - начало цепочки
        for (int j=0;j<i;j++)
        {
            if (maxP[j] !=0) // j-ый гангстер смог зайти, значит i-ый        [возможно] сможет продолжить цепочку заканчивающуюся j-ым гангстером
{
                int dt = t[i] - t[j];
                int dk = abs(s[i] - s[j]);
                if (dk<=dt) // если [true], то [точно сможет] продолжить
                    curMaxPayment = max(curMaxPayment,maxP[j]+p[i]);
            }
        }
        maxP[i] = curMaxPayment;
    }
}
void output()
{
    cout<<*max_element(maxP.begin(),maxP.end());
}
int main()
{
    input();
    solve();
    output();
    return 0;
}

         

Администратор Photo Автор: Администратор


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

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться