Pagini recente » Cod sursa (job #796811) | Cod sursa (job #606708) | Cod sursa (job #885276) | Cod sursa (job #1234050) | Cod sursa (job #1017393)
#include <iostream>
#include <stdio.h>
using namespace std;
// idee: se fixeaza coloanele sau liniile (una dintre) cu backtr. => toate posibilitatile
// pt fiecare posibilitate fixata, acum pot sa utilizez greedy si sa iau doar varianta cea mai buna pentru coloane.
// inainte nu puteam fiindca deciziile nu erau independente, se intrepatrundea linia cu coloana (un element comun)
int n, m, M[20][20], sScenariu1 = 0, sScenariu2 = 0, sMax = 0, aux, aux1;
int posibilitate[] = { -1, 1 };
int combinatii[50];
void citireFis() {
scanf("%d %d", &n, &m);
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
scanf("%d", &M[i][j]);
}
void calcSumaScenariu(int col) {
sScenariu1 = 0;
sScenariu2 = 0;
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; j++) {
aux1 = M[i][j];
if (j == col) {
aux = aux1;
sScenariu1 += (aux * combinatii[i] * (-1));
}
else {
sScenariu1 += (aux1 * combinatii[i]);
}
sScenariu2 += (aux1 * combinatii[i]);
}
if (sScenariu1 > sMax)
sMax = sScenariu1;
if (sScenariu2 > sMax)
sMax = sScenariu2;
}
void greedy() {
for(int i = 0; i < m; ++i)
calcSumaScenariu(i);
}
void backTracking(int k) {
if(k == n) {
greedy();
} else {
for(int i = 0; i < 2; ++i) {
combinatii[k] = posibilitate[i];
backTracking(k + 1);
}
}
}
int main() {
freopen("flip.in", "r", stdin);
freopen("flip.out", "w", stdout);
citireFis();
backTracking(0);
printf("%d", sMax);
return 0;
}