Pagini recente » Cod sursa (job #2585273) | Cod sursa (job #600097) | Cod sursa (job #462523) | Cod sursa (job #145625) | Cod sursa (job #2383416)
/*
D[i] = suma din primele i cutii doar cu secvente de cate exact doua vecine
- pot gandi D[i] ca mai sus si obligatoriu cu ultima valoare aleasa
- pot gandi fara sa oblig sa fi fost aleasa ultima valoare
Sa analizam semnificatia lu D[i] in al doilea caz
D[i]
- fie aleg din ultimele doua cutii, v[i]+v[i-1]+D[i-3]
- nu iau din ultima cutie D[i-1]
D[1] = 0;
D[2] = v[1] + v[2];
D[3] = max(v[1]+v[2], v[2]+v[3]);
for (i=;i<=n;i++)
D[i] = max(D[i-1], v[i]+v[i-1] + D[i-3]);
Pentru sir circular:
1. Nu iau in calcul ultimul element la dinamica de mai sus
adica fac dinamica de mai sus si consider D[n-1]
2. Nu iau in calcul primul element si inseamna ca fac initializarile altfel
D[1] = 0;
D[2] = 0;
D[3] = v[2]+v[3];
fac dinamica normal si iau in calcul pe D[n]
3. Iau in calcul cazul cu primul si ultimul sigur in solutie
Deci nu voi lua nici pe v[2] nici pe v[n-1]
D[1] = 0;
D[2] = 0;
D[3] = 0;
D[n-2] + V[1]+V[n]
*/
#include <fstream>
using namespace std;
ifstream fin ("oo.in");
ofstream fout("oo.out");
int D[100001],v[100001];
int n,sol,i;
int main(){
fin>>n;
for(i=1;i<=n;i++)
fin>>v[i];
D[1]=0;
D[2]=v[1]+v[2];
D[3]=max(v[1]+v[2],v[2]+v[3]);
for(i=4;i<n;i++)
D[i]=max(D[i-1],v[i]+v[i-1]+D[i-3]);
sol=D[n-1];
D[1]=0;
D[2]=0;
D[3]=v[2]+v[3];
for(i=4;i<=n;i++)
D[i]=max(D[i-1],v[i]+v[i-1]+D[i-3]);
sol=max(sol,D[n]);
D[1]=0;
D[2]=0;
D[3]=0;
for(i=4;i<n-1;i++)
D[i]=max(D[i-1],v[i]+v[i-1]+D[i-3]);
sol=max(sol,D[n-2]+v[1]+v[n]);
fout<<sol;
return 0;
}