Solução Informática Intermediário - Semana 64

Solução por Leonardo Paes

Para resolver este problema, utilizaremos programação dinâmica.

Seja $dp[i][j]$ a soma máxima de alturas de um time que começa com o $j$ -ésimo estudante da fileira $i$ e pode escolher jogadores com índices maiores que $j$ . Logo, a resposta de nosso problema será: $max(dp[1][1], dp[2][1])$ .

Seja $i'$ uma representação da fileira oposta a fileira $i$ , ou seja, se $i = 1, i' = 2$ , e vice-versa. Para calcularmos a recursão, teremos: $dp[i][j] = h[i][j] + max(dp[i'][j+1], dp[i'][j+2])$ , onde $h[i][j]$ é a altura do $j$ -ésimo estudante da fileira $i$ .

Segue abaixo o código para melhor entendimento:

	#include <bits/stdc++.h>

	using namespace std;

	const int maxn = 1e5+100;

	int n, h[3][maxn];

	long long dp[3][maxn];

	long long solve(int fila, int col){
	if(col>=n)return dp[fila][col] = h[fila][col];
	if(dp[fila][col]!=-1) return dp[fila][col];
	long long caso1, caso2;
	if(fila==1){
	caso1 = solve(2, col+1);
	caso2 = solve(2, col+2);
	}
	if(fila==2){
	caso1 = solve(1, col+1);
	caso2 = solve(1, col+2);
	}
	return dp[fila][col] = h[fila][col] + max(caso1, caso2);
	}

	main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

	cin >> n;

	for(int i=1; i<=2; i++){
	for(int j=1; j<=n; j++){
	cin >> h[i][j];
	}
	}

	memset(dp, -1, sizeof dp);

	solve(1, 1);
	solve(2, 1);

	long long resp = max(dp[1][1], dp[2][1]);

	cout << resp << endl;
	}

view raw Exercício de Basquete.cpp hosted with ❤ by GitHub