Pagini recente » Cod sursa (job #3238953) | Cod sursa (job #319478) | Cod sursa (job #2908668) | Cod sursa (job #1358395) | Cod sursa (job #2749131)
/**
generez toate sirurile de 0 si 1 cu exact care 2 de 1 vecini
3 4 0 1 0 6 7 1 2 1
0 1 1 0 0 1 1 0 1 1
**/
#include <fstream>
using namespace std;
int v[100010], x[100010];
int n, sol, i;
int cont(int pas) {
if (pas >= 3) {
if (x[pas] == 1 && x[pas-1] == 1 && x[pas-2] == 1)
return 0;
if (x[pas] == 0 && x[pas-1] == 1 && x[pas-2] == 0)
return 0;
}
return 1;
}
void backtrack(int pas) {
/// toate sirurile de lungime n cu 0 si 1
/// cu exact cate 2 de 1 vecini (circulare)
if (pas > n) { /// sol are n elemente
if (x[n] == 1 && x[n-1] == 1 && x[1] == 1)
return;
if (x[n] == 1 && x[1] == 1 && x[2] == 1)
return;
if (x[n] == 1 && x[1] == 0 && x[n-1] == 0)
return;
if (x[1] == 1 && x[2] == 0 && x[n] == 0)
return;
int suma = 0;
for (int i=1;i<=n;i++)
if (x[i] == 1)
suma += v[i];
if (suma > sol)
sol = suma;
} else {
for (int i=0;i<=1;i++) { /// orice element din solutie poate fi 0 sau 1
x[pas] = i;
if (cont(pas))
backtrack(pas+1);
}
}
}
int main () {
ifstream fin ("oo.in");
ofstream fout("oo.out");
fin>>n;
for (i=1;i<=n;i++)
fin>>v[i];
backtrack(1);
fout<<sol;
return 0;
}