Solução de Roger Benet comentário por João Guilherme
Essa é uma questão de programação dinâmica(pd), para ver a aula do Noic sobre pd, clique aqui. Primeiro ordenamos os intervalos pelos seus fins, depois fazemos uma dp com os parâmetros índice que estamos olhando e tempo atual, com cada estado recebendo a máximo entre não usar o intervalo de índice i e, se possível, usar tal intervalo . Por fim, o caso de base é quando o índice é maior que o número de intervalos, nesse caso retornamos 0.
Segue código para melhor entendimento.
This file contains 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; | |
| #define MAXN 1010 | |
| pair <int,int> pi[MAXN]; | |
| int dp[MAXN][3610]; | |
| int n; | |
| int solve(int atual, int tempo){ | |
| if(atual >= n)return 0; | |
| if(dp[atual][tempo] >= 0)return dp[atual][tempo]; | |
| int davez = 0, prox = 0; | |
| prox = solve(atual+1,tempo); | |
| if(pi[atual].second >= tempo) | |
| davez = pi[atual].first - pi[atual].second + solve(atual+1,pi[atual].first); | |
| return dp[atual][tempo] = max(davez,prox); | |
| } | |
| int main(){ | |
| scanf("%d", &n); | |
| memset(dp,-1,sizeof(dp)); | |
| for(int p = 0; p < n; p++){ | |
| int i,j; | |
| scanf("%d %d", &i, &j); | |
| pi[p].first = j, pi[p].second = i; | |
| } | |
| sort(pi,pi+n); | |
| printf("%d\n",solve(0,0)); | |
| return 0; | |
| } |