Pagini recente » Cod sursa (job #1649920) | Cod sursa (job #2941272) | Cod sursa (job #2761289) | Cod sursa (job #1697853) | Cod sursa (job #855319)
Cod sursa(job #855319)
#include <fstream>
using namespace std;
//Vectorul initial, cel in care tinem datele de intrare
int v[100005];
//Functie de maxim
int maxim(int a,int b)
{
if(a>b)
return a;
return b;
}
//Functie care face calculul pe un sir liniar, la adresa v si de lungime n
int dinamica(int *v,int n)
{
//Pentru 0 si 1 nu avem combinatii
if(n<2)
return 0;
//Pentru 3 calculul este foarte simplu
if(n==3)
return (maxim(v[n-3],v[n-1])+v[n-2]);
//In m vom tine maximul de la i pana la sfarsit
int m[100005];
//Cazurile de baza
m[n-1]=0;
m[n-2]=v[n-1]+v[n-2];
m[n-3]=maxim(v[n-3],v[n-1])+v[n-2];
//Implementarea relatiei de recurenta
int i;
for(i=n-4;i>=0;i--)
m[i]=maxim(m[i+1],m[i+3]+v[i]+v[i+1]);
//Raspunsul se afla pe m[0]
return m[0];
}
int main()
{
//Deschiderea fisierelor de intrare si iesire
ifstream fin("oo.in");
ofstream fout("oo.out");
//Variabile locale
int n,i,x,sulutie=0;
//Se citesc cotetele
fin>>n;
for(i=0;i<n;i++)
fin>>v[i];
//Avem 4 cazuri cand folosim primul sau ultimul cotet
x=dinamica(v+3,n-4)+v[0]+v[1];
if(x>solutie)
solutie=x;
x=dinamica(v+2,n-4)+v[0]+v[n-1];
if(x>solutie)
solutie=x;
x=dinamica(v+1,n-4)+v[n-1]+v[n-2];
if(x>solutie)
solutie=x;
//Si cazul cand nu ne folosim de acestea
x=dinamica(v+1,n-2);
if(x>solutie)
solutie=x;
//Afisam solutia
fout<<solutie<<'\n';
//Inchidem fisierele de intrare si iesire
fin.close();
fout.close();
return 0;
}