Solução por Pedro Racchetti
Conhecimentos utilizados:
Para esse problema, temos que primeiro notar que, para qualquer resposta, podemos sempre transformar os caminhos de forma que o caminho de ida nunca esteja estritamente abaixo e a esquerda do caminho de volta, já que as mesmas ruas serão atravessadas, e os mesmos quarteirões serão cercados. Isso nos ajuda, pois agora podemos considerar que o caminho de ida irá somar na resposta todos os quarteirões que estão abaixo dele, e o de volta irá subtrair os quarteirões, ou seja, no final estaremos apenas somando os quarteir!oes entre os caminhos! Podemos fazer isso de forma rápida, pré-calculando as somas de prefixo em uma coluna, indo de baixo para cima. Chamaremos esses vetores de $$pref[i][j]$$, guardando a soma de quarteirões posicionados abaixo $$j$$, na $$i$$-ésima coluna + $$A_{i,j}$$.
Podemos então aplicar programação dinâmica, com duas recursões, de forma que uma calcule o melhor caminho de ida ($$DP_{ida}$$), e uma que calcule o melhor caminho de volta ($$DP_{volta}$$), com os estados sendo a posição atual. Note que como os valores são sempre positivos, a segunda recursão sempre escolherá um caminho de volta válido, como descrito anteriormente. As equações de transição são as seguintes:
- $$DP_{ida}(x, y) = max(DP_{ida}(x,y+1) + pref[x][y] – H_{x,y},$$ $$DP_{ida}(x+1,y) – V_{x,y})$$, já que essa recursão pode escolher ir para a direita, somando uma nova coluna ou descer.
- $$DP_{volta}(x, y) = max(DP_{volta}(x,y+1) – pref[x][y] – H_{x,y},$$ $$DP_{ida}(x+1,y) – V_{x,y})$$, já que essa recursão pode escolher ir para a direita, somando uma nova coluna ou descer.
A base para ambas as recursões, a base está em $$x = n$$ e $$y = m$$, onde ambas valem zero, já que não há o que adicionar. A resposta final é $$DP_{ida}(0,0) – DP_{volta}(0,0)$$
Segue o código, comentado, para melhor compreensão.
| #include <bits/stdc++.h> | |
| using namespace std; | |
| const int INF = 1e9 + 7; | |
| // usaremos o INF como um indicador que ainda não calculamos | |
| // o estado. Note que não podemos usar artificios como -1 | |
| // pois a recursão aceita valores negativos | |
| int A[212][212], pref[212][212]; | |
| int H[212][212], V[212][212]; | |
| int n, m; | |
| int dp_ida[212][212]; | |
| int dp_volta[212][212]; | |
| int fazdp_ida(int x, int y){ | |
| //verificamos se já calculamos o estado atual, ou se essa é a base da recursão | |
| if(x == n && y == m) return 0; | |
| if(dp_ida[x][y] != INF) return dp_ida[x][y]; | |
| //se estamos na ultima linha ou coluna, podemos apenas ir para a direita ou para baixo, respectivamente. | |
| if(x == n) return dp_ida[x][y] = fazdp_ida(x, y + 1) – H[x][y]; | |
| if(y == m) return dp_ida[x][y] = fazdp_ida(x+ 1 , y) – V[x][y]; | |
| //calculamos os dois valores possíveis para essa recursão, indo pa a direita | |
| //e adicionando uma nova coluna, ou descemos para a próxima linha | |
| int ans1, ans2; | |
| ans1 = fazdp_ida(x, y + 1) + pref[x][y] – H[x][y]; | |
| ans2 = fazdp_ida(x + 1, y) – V[x][y];; | |
| return dp_ida[x][y] = max(ans1, ans2); | |
| } | |
| int fazdp_volta(int x, int y){ | |
| //verificamos se já calculamos o estado atual, ou se essa é a base da recursão | |
| if(x == n && y == m) return 0; | |
| if(dp_volta[x][y] != INF) return dp_volta[x][y]; | |
| //se estamos na ultima linha ou coluna, podemos apenas ir para a direita ou para baixo, respectivamente. | |
| if(x == n) return dp_volta[x][y] = fazdp_volta(x, y + 1) – H[x][y]; | |
| if(y == m) return dp_volta[x][y] = fazdp_volta(x + 1, y) – V[x][y]; | |
| //calculamos os dois valores possíveis para essa recursão, indo pa a direita | |
| //e adicionando uma nova coluna, ou descemos para a próxima linha | |
| int ans1 = fazdp_volta(x, y + 1) – pref[x][y] – H[x][y]; | |
| int ans2 = fazdp_volta(x + 1, y) – V[x][y]; | |
| return dp_volta[x][y] = max(ans1, ans2); | |
| } | |
| int main(){ | |
| //inicializamos as DPs como infinita, pra mostrar que ainda não lemos. | |
| scanf("%d %d", &n, &m); | |
| for(int i = 0; i <= n; i++) | |
| for(int j = 0; j <= m; j++) | |
| dp_ida[i][j] = INF, dp_volta[i][j] = INF; | |
| //lemos a entrada | |
| for(int i = 0; i < n; i++) | |
| for(int j = 0; j < m; j++) | |
| scanf("%d", &A[i][j]); | |
| for(int i = 0; i <= n; i++) | |
| for(int j = 0; j < m; j++ ) | |
| scanf("%d", &H[i][j]); | |
| for(int i = 0; i <= m; i++) | |
| for(int j = 0; j < n; j++) | |
| scanf("%d", &V[j][i]); | |
| //pré-calculamos as somas de prefixo | |
| for(int i = 0; i < m; i++) | |
| for(int j = n – 1; j >= 0; j–) | |
| pref[j][i] = pref[j+1][i] + A[j][i]; | |
| int ans = fazdp_ida(0, 0) + fazdp_volta(0, 0); //note que aqui somamos a volta, pois essa já é negativa | |
| printf("%d\n", ans); | |
| } |
