# PBinfo #1095 – Joc4 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

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

## Cod sursă C++

```cpp
/*
	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();
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1095)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1095/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1095/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)