Rezolvare completă PbInfo #1095 Joc4

Jocul nostru presupune parcurgerea unui tablou bidimensional cu două linii şi n coloane, format din 2•n celule pătratice. Fiecare celulă are asociată câte o valoare întreagă v care nu se modifică pe durata desfăşurării jocului. Jucătorii trebuie să găsească un drum de la celula de plecare la celula de sosire care respectă următoarele condiţii:

  • celula de plecare este cea din linia 1 şi coloana 1, iar celula de sosire este cea din linia 2 şi coloana n.
  • nu trece decât cel mult odată prin oricare celulă.
  • deplasarea se poate face din celula curentă spre oricare altă celulă învecinată cu ea pe orizontală sau verticală.
  • conţine cel mult k celule consecutive aflate pe aceeaşi linie.

Pentru un astfel de drum se calculează punctajul acestuia ca fiind egal cu suma valorilor asociate celulelor prin care trece drumul.

Cerinţă

Cunoscând valorile asociate celulelor tabloului, scrieţi un program care determină punctajul maxim care poate fi obţinut în acest joc.

Date de intrare

Fișierul de intrare joc4.in conține pe prima linie două numere naturale n şi k separate printr-un spaţiu cu semnificaţiile din enunţ. Pe fiecare dintre următoarele două linii se găsesc câte n numere întregi, reprezentând valorile asociate celor 2•n celule ale tabloului.

Date de ieșire

Fișierul de ieșire joc4.out va conține pe prima linie numărul întreg p, reprezentând punctajul maxim care se poate obţine.

Restricții și precizări

  • 2 ≤ n ≤ 5000
  • 2 ≤ k ≤ 10, k ≤ n
  • -1000 ≤ v ≤ 1000
  • Pentru 40% dintre cazurile de test n ≤ 40

Exemple



joc4.in

6 3
0 -2 5 4 -9 -1
-1 3 2 7 0 1

joc4.out

21

Explicație

Jucătorul va parcurge în ordine celulele cu valorile:
0, -1, 3, 2, 5, 4, 7, 0, 1.

joc4.in

5 5
0 0 4 2 10 
2 -3 -8 6 -2

joc4.out

14

Explicație

Jucătorul va parcurge în ordine celulele cu valorile:
0, 0, 4, 2, 10, -2

joc4.in

5 4
-3 0 5 4 10 
-2 3 -2 7 0

joc4.out

22

Explicație

Jucătorul va parcurge în ordine celulele cu valorile:
-3,-2, 3, 0, 5, -2, 7, 4, 10, 0

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Joc4:

/*
    Recursie cu memoizare
    Complexitate: O(n * k)
    Constantin Galatan
*/
#include <fstream>
#include <climits>
using namespace std;

#define INF INT_MAX / 2
#define sus 0
#define dr  1
#define jos 2

ifstream fin("joc4.in");
ofstream fout("joc4.out");

int a[2][5001];
int n;
int K;
int s[2][5001][3][11];              // s[l][c][dir][k] - suma maxima pana la linia l, coloana c, daca s-a intrat in
                                    //                   celula din directia dir, cu k celule consecutive pe linia l
void Read();
int Sum(int l, int c, int d, int k);
int max(int a, int b);

int main()
{
    Read();

    fout << Sum(1, n - 1, dr, 1) << '\n';

    fout.close();
    return 0;
}

int Sum(int l, int c, int dir, int k)
{
    int& ret = s[l][c][dir][k];     // ret - alias pentru s[l][c][dir][k];

    if ( ret != -INF )              // Daca se trece printr-o stare anterior calculata
        return ret;                 // se returneaza valoarea din matrice

    if ( l == 0 && c == 0 ) return ret = a[0][0];
    if ( l == 1 && c == 0 ) return ret = a[l][c] + a[0][0];

    // Suma maxima se calculeaza in functie de linia curenta, directia din care s-a intrat in celula
    // si numarul de celule consecutive  parcurse pe linie
    int r(0);
    if ( l == 1 )
    {
        if ( dir == dr )
            if ( k < K  )
                r = max(Sum(l, c - 1, dr, k + 1), Sum(l - 1, c, jos, 1));
            else
                r = Sum(l - 1, c, jos, 1);

        if ( dir == sus )
            r = Sum(l, c - 1, dr, k + 1);
    }

    if ( l == 0 )
    {
        if ( dir == dr )
            if ( k < K )
                r = max(Sum(l, c - 1, dr, k + 1), Sum(l + 1, c, sus, 1));
            else
                r = Sum(l + 1, c, sus, 1);

        if ( dir == jos) r = Sum(l, c - 1, dr, k + 1);
    }

    return ret = r + a[l][c];
}

int max(int a, int b)
{
    if ( a >= b ) return a;
    return b;
}

void Read()
{
    int i(0), j(0);
    fin >> n >> K;
    for ( i = 0; i < 2; ++i )
        for ( j = 0; j < n; ++j )
            fin >> a[i][j];

    for ( i = 0; i < 2; ++i )
        for ( j = 0; j < n; ++j )
            for ( int d = 0; d < 3; ++d )
                for (int k = 0; k <= K; ++k )
                s[i][j][d][k] = -INF;

    fin.close();
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #1095 Joc4

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1095 Joc4 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!