Created
April 12, 2016 12:42
-
-
Save rogerioagjr/152aa53ed240065be71333a0ba6ab9a5 to your computer and use it in GitHub Desktop.
Cartões
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 <cstdio> | |
| #include <cstring> | |
| #include <algorithm> | |
| #define MAXN 10010 | |
| using namespace std; | |
| typedef long long int lli; | |
| // função que retorna o resto (positivo) de um número módulo 3 | |
| int mod(int x){ | |
| int a=x%3; | |
| if(a<0) return a+3; | |
| return a; | |
| } | |
| lli n, vetor[MAXN], tab[MAXN][3]; | |
| // Função que calcula a DP Bottom-Up | |
| lli dp(){ | |
| for(int fim=1; fim<=n; fim++) | |
| for(int ini=n; ini>=1; ini--){ | |
| // se fim<ini, retorn 0 | |
| if(fim<ini) tab[ini][mod(fim)]=0; | |
| // caso contrário, retorne o melhor entre tirar o cartão do início ou do fim | |
| if(fim>ini) tab[ini][mod(fim)]=max(vetor[ini]+min(tab[ini+2][mod(fim)], tab[ini+1][mod(fim-1)]), vetor[fim]+min(tab[ini+1][mod(fim-1)], tab[ini][mod(fim-2)])); | |
| } | |
| // por fim, retorne o último valor calculado | |
| return tab[1][mod(n)]; | |
| } | |
| int main(){ | |
| // enquanto houver entrada | |
| while(scanf("%lld", &n)!=EOF){ | |
| // limpe a tabela de DP | |
| memset(tab, 0, sizeof(tab)); | |
| // leia os valores dos cartões | |
| for(lli i=1; i<=n; i++) scanf("%lld", &vetor[i]); | |
| // e imprima o resultado da DP | |
| printf("%lld\n", dp()); | |
| } | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
quero comprar numeros aonde faço isso fico grato