Cod sursa(job #1017407)

Utilizator Alina_MariaMateescu Adina Lenuta Maria Alina_Maria Data 27 octombrie 2013 19:12:30
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#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, sumaTotalaCurenta = 0;
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) {
        aux1 = M[i][col];
        aux = M[i][col];
        sScenariu1 += (aux * combinatii[i] * (-1));
        sScenariu2 += (aux1 * combinatii[i]);
    }
    if (sScenariu1 > sScenariu2)
        sumaTotalaCurenta += sScenariu1;
        else
            sumaTotalaCurenta += sScenariu2;
}

void greedy() {
    sumaTotalaCurenta = 0;
    for(int i = 0; i < m; ++i)
        calcSumaScenariu(i);
    if (sumaTotalaCurenta > sMax)
        sMax = sumaTotalaCurenta;
}

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;
}