1236 Controlor

[•wefgef]

Aici puteti discuta despre problema Controlor.

[•soriyn]

Imi explica si mie cineva de ce pentru 2,1 raspunsul e 15 ? E destul de ambiguu enuntul.

[•wefgef]

Ce este ambiguu in enunt?

Cati calatori se afla in tren intre statiile 2 si 3? Cati dintre ei se aflau deja in tren inainte de statia 2?

[•PlayLikeNeverB4]

La (2,1) trebuie sa spui cate persoane se afla in tren intre statiile (2,3) si trebuie sa iei in considerare doar persoanele care au urcat dupa sau la statia 2. La statia 2 urca 5+6+4=15 persoane si doar pe acestea le luam in considerare.

[•feel.good1802]

Am o intrebare... imi explicati va rog frumos cum se face pentru linia i=2?
Eu am ca la m[2][1]=15 si m[2][2]=20 m[2][3]=13... nu inteleg cum se face calculul...

[•thesilverhand13]

In primul rand,la aceasta problema tu nu trebuie sa abordezi cu o rezolvare pe linii,ci pe coloane...
Trebuie sa utilizezi o matrice dp[ i ][ j ] care sa semnifice numarul de calatori prezenti in tren la statia i + j ,presupunand ca Miruna verifica biletele la statia i.
Este destul de intuitiv faptul ca pentru coloana 1,adica pentru dp[ 1 ][ 1 ], dp[ 2 ][ 1 ]...vom aduna numarul tuturor calatorilor de pe linia respectiva.Iar pentru coloanele 2, 3....respectiv n - 1 vom avea urmatoarea relatie: dp[ i ][ j ] = dp[ i ][ 1 ] - ( a[ i ][ 1 ] + a[ i ][ 2 ] + ........ + a[ i ][ j ] ) + dp[ i + 1 ][ j - 1 ];Mentionez ca in matricea a tu citesti valorile respective din fisierul de intrare.
Bineinteles...se poate reduce complexitatea cu o alta matrice de sume partiale.Dar aici te las pe tine  .

[•rares96cheseli]

Pentru cei care iau 70p cu TLE pe ultimele 3 teste, afisati cu cstdio.