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:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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; | |
| } |