Cod sursa(job #855322)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 14 ianuarie 2013 21:16:37
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#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,solutie=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;
}