087 Gard

[•domino]

Aici puteţi discuta despre problema Gard.

[•Marius]

ce complexitate ati gasit la problema asta ? eu am N * N * K, ceea ce e destul de mult...    cum pot sa scap de un N ?

[u-92]

cu cateva observatii utile devine N*K
daca nu te prinzi, problema asta a fost data la oni 2002 la baraj (dupa cum scrie si in enunt )

[•hendrik]

Hi,
I am stuck in this problem  , could someone explain how to solve it in O(N*K)?

Thanks

Hi,
I am stuck in this problem  , could someone explain how to solve it in O(N*K)?

Thanks

any body here? Please help me

It would be nice if you would edit your previous messages when consecutively posting on the same subject.

ah.. sorry for that. Ok I will do it from now on. Thx for the advice

[•SpiderMan]

I can give you the official source, if it helps you 

[•hendrik]

hm.. thx for replying . I would be happy if someone can give me some hints and I tried it myself 

[•pauldb]

I can't remember the exact details, but you should use a deque in order to improve the DP to run in O(N*K). If this hint is doesn't help you enough, I'll think of the problem in a couple of days and post a more detailed solution.

[•hendrik]

I can't remember the exact details, but you should use a deque in order to improve the DP to run in O(N*K). If this hint is doesn't help you enough, I'll think of the problem in a couple of days and post a more detailed solution.

hm.. I still don't get the idea how to solve it with a deque Further helps needed

[•stardust]

Salut ! Am nevoie de putin ajutor la problema asta. Eu m-am gandit asa. dp[ i ][j] - suma maxima ce se poate obtine daca ultima scandura vopsita de muncitorul i este j. Doar ca ma incurc cand trebuie sa fac deque-ul. De fapt, mai general, chestia e urmatoarea : am un vector cu n numere. Si pentru o pozitie fixata x stiu ca pot sa merg inapoi y pozitii. Imi trebuie maximul dintre a[x-i]+c*i, unde c constat si 1<=i<=y. Se poate face asta cu deque ? Si daca da cum ?

Si daca nu se poate cam cum ar trebui rezolvata problema ?

[•tzipleatud]

Salut! Nu am facut problema asta, dar cred ca iti pot raspunde la intrebarea ta in legatura cu deque. Avand in vedere ca fiecare element "creste" constant cu C, la fiecare pas, rezulta ca ordinea elementelor din deque nu se va modifica. Uite o portiune de cod:

Cod:

#include <iostream>
#include <deque>

using namespace std;

int N,i,C,Y;
int A[1010];
deque<int> D;

int main ()
{
    cin >> N >> C >> Y;
    for (i=1; i<=N; i++)
        cin >> A[i];

    for (i=1; i<=N; i++)
    {
        while (!D.empty() && A[D.back()]+C*(i-D.back())<=A[i]) D.pop_back(); //scot cat timp A[i] reprezinta o solutie mai buna
        while (!D.empty() && i-D.front()>Y) D.pop_front(); // scot cat timp solutia nu se afla in intervalul [X-Y,X]
        D.push_back(i);
        cout << "Maximul la pozitia " << i << " este " << (A[D.front()]+C*(i-D.front())) << '\n';
    }

    return 0;
}

Cam asa ceva ar veni, sper ca nu am gresit nimic. Bafta!