Solução Informática - Nível Avançado - Semana 15

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);

	}

view raw

burnmanhootam.cpp

hosted with ❤ by GitHub