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

Chamemos de $val[]$ o vetor que guarda o preço das ações em cada dia.

Para este problema, faremos uma dp com dois parâmetros:

Com isso, teremos que $dp[u][mod] = max(p1, p2)$ , sendo:

$p1$ : caso eu já possua uma ação, irei vendê-la, logo $p1 = val[u] + dp[u+1][0]$ . Caso eu não possua, irei comprá-la. Então $p1 = - val[u] - c + dp[u+1][1]$ , pois tenho que pagar o valor da ação e o valor $c$ fixo.
$p2$ : não faço nada nesse dia, então $p2 = dp[u+1][mod]$ .

No fim, basta imprimirmos a resposta de $dp[1][0]$ . Segue o código para melhor entendimento:

	#include <bits/stdc++.h>
	using namespace std;

	const long long int maxn = 2e5+10, inf = 1e18;

	long long int n, c, val[maxn], dp[maxn][2];

	long long int solve(int u, int mod)
	{
	if(dp[u][mod] != inf) return dp[u][mod]; //se ja calculei esse caso, retorno a dp

	if(u == n+1) return 0; //ja olhei todos os dias, então retorno 0

	long long int p1, p2;

	if(!mod) p1 = - val[u] - c + solve(u+1, 1);
	else p1 = val[u] + solve(u+1, 0);

	p2 = solve(u+1, mod);

	return dp[u][mod] = max(p1, p2);
	}

	int main()
	{
	while(cin >> n >> c)
	{
	for(int i = 0 ; i < maxn ; i++)
	{
	dp[i][0] = dp[i][1] = inf; //declaro que ainda não calculei nenhum dos casos, igualando todos a inf
	}

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

	long long int resp = solve(1, 0);
	cout << resp << "\n";
	}
	}

view raw

s69_avançado.cpp

hosted with ❤ by GitHub