Pagini recente » Cod sursa (job #897333) | Cod sursa (job #1459008) | Cod sursa (job #554462) | Cod sursa (job #985737) | Cod sursa (job #618472)
Cod sursa(job #618472)
#include<fstream>
using namespace std;
ofstream fout("flip.out");
long lin,col, sumaMax = -1<<29, sumaInitiala;
long sumaLin[20],sumaCol[20];
long a[20][20];
inline int SumaLin(int i)
{
int s=0;
for (int j=1;j<=col;j++)
s+=a[i][j];
return s;
}
inline int SumaCol(int j)
{
int s=0;
for (int i=1;i<=lin;i++)
s+=a[i][j];
return s;
}
//Calc suma initiala pe fiecare linie, coloana si a intregii matrice
void CalculeazaSumeInitiale()
{
int i;
for (i=1;i<=lin;i++) sumaLin[i] = SumaLin(i);
for (i=1;i<=col;i++) sumaCol[i] = SumaCol(i);
for (i=1;i<=lin;i++) sumaInitiala += sumaLin[i];
sumaMax = sumaInitiala;
}
int stivaIndici[40]; //punem indicii de la 1 la lin pentru linii si de la lin+1 la lin+col pentru coloane
int stivaSume[40]; //punem suma initiala corespunzatoare liniei sau coloanei reprezentata in stivaIndici
//un candidat este valid pentru a fi pus pe stiva daca este mai mare decat ultimul element adaugat
bool EValid(int top, int candidat)
{
if (top == 1) return true;
if (candidat > stivaIndici[top - 1]) return true;
return false;
}
//daca liniile si coloanele de pe stiva genereaza , prin flip, o suma mai mare, actualizeaza
void ActualizeazaMax(int k)
{
int i, sumaTemp = sumaInitiala;
for (i=1;i<=k;i++)
sumaTemp += (-2) * stivaSume[i];
if (sumaTemp > sumaMax) sumaMax = sumaTemp;
/*
for (i = 1; i <= k; i++) fout<<stivaSume[i]<<" ";
fout<<"\t-->\t";
for (i=1;i<=k;i++)
fout<<stivaIndici[i]<<" ";
fout<<"\t\t\t"<<sumaTemp<<"\n";
*/
}
//Generam Combinari de lin+col luate cate k, k=1,lin+col-1
void Back(int top, int k)
{
if (top == k+1) ActualizeazaMax(k);
else
{
int i;
for (i=1;i<=lin+col;i++)
if (EValid(top,i))
{
stivaIndici[top] = i;
stivaSume[top] = i <= lin ? sumaLin[i]: sumaCol[i - lin];
Back(top+1,k);
}
}
}
int main()
{
int k;
ifstream fin("flip.in");
fin>>lin>>col;
int i,j;
for (i=1;i<=lin;i++)
for (j=1;j<=col;j++)
fin>>a[i][j];
fin.close();
CalculeazaSumeInitiale();
for (k=1;k<=lin+col-1;k++)
Back(1,k);
fout<<sumaMax<<"\n";
fout.close();
return 0;
}