Solução por Sofhia Souza
Conhecimento prévio: Programação dinâmica
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:
- $$u$$: representa o $$u$$-ésimo dia
- $$mod$$: se nesse dia $$u$$ eu já possuo(1) ou não(0) uma ação da empresa
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:
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 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"; | |
| } | |
| } |