Solução Informática Avançado - Semana 64

Solução por Lúcio Cardoso

Seja $dp[i][0]$ o menor custo para derrubar todos os pilares de $1$ a $i$ e $dp[i][1]$ o menor custo para derrubar todos os pilares de $1$ a $i$ , assumindo que o pilar $i+1$ foi derrubado antes do pilar $i$ .

Assim,

$dp[i][0] = min(dp[i-1][1] + d[i], dp[i-1][0] + max(0, d[i]-w[i-1]))$ .

Ou seja, analisamos as respostas analisando se o pilar $i$ foi derrubado antes ou depois do pilar $i-1$ .

Além disso,

$dp[i][1] = min(dp[i-1][1] + max(0, d[i]-w[i+1]), dp[i-1][0] + max(0, d[i]-w[i]-w[i+1]))$ .

Novamente, analisamos cada um dos casos dentre derrubar $i$ antes ou depois de $i-1$ , sabendo que $i+1$ já foi derrubado.

A resposta final do problema será $dp[N][0]$ , e é fácil perceber que a complexidade final é $O(n)$ .

	// Noic - Semana 64 - Avançado
	// Complexidade: O(n)

	#include <bits/stdc++.h>

	using namespace std;

	const int maxn = 1e5+10;

	typedef long long ll;

	int d[maxn], w[maxn];

	ll dp[maxn][2];

	int main(void)
	{
	int n;
	cin >> n;

	for (int i = 1; i <= n; i++)
	cin >> d[i] >> w[i];

	// casos base
	dp[1][0] = d[1], dp[1][1] = max(0, d[1]-w[2]);

	for (int i = 2; i <= n; i++)
	{
	// possibilidades para dp[i][0]
	ll b1 = 1LL*d[i] + dp[i-1][1];
	ll b2 = dp[i-1][0] + 1LL*max(0, d[i]-w[i-1]);

	dp[i][0] = min(b1, b2);

	// perceba que se i = n, não há pilar i+1
	if (i < n)
	{
	// possibilidades para dp[i][1]
	ll c1 = 1LL*max(0, d[i]-w[i+1]) + dp[i-1][1];
	ll c2 = dp[i-1][0] + 1LL*max(0, d[i]-w[i-1]-w[i+1]);

	dp[i][1] = min(c1, c2);
	}
	}

	// resposta do problema
	cout << dp[n][0] << "\n";
	}

view raw noic-s64-avancado.cpp hosted with ❤ by GitHub