Pagini recente » Cod sursa (job #1144543) | Cod sursa (job #1925350) | Cod sursa (job #660761) | Cod sursa (job #1739239) | Cod sursa (job #66548)
Cod sursa(job #66548)
// flip, infoarena
// avand o matrice cu numere trebuie obtinuta suma maxima; matricea are 16 linii si 16 coloane max.
// se pot comuta (inmulti cu -1) coloane sau linii
// generez toate modurile de a comuta linii
// comut acele coloane care prin comutare dau o suma mai mare
#include <cstdio>
#include <cmath>
const int MAX_N = 16;
int A[MAX_N][MAX_N],B[MAX_N][MAX_N], M, N, bsum = 0;
bool com[MAX_N];
void check(void) {
int sum = 0, ysum, nsum, i, j, c;
for (i = 0; i < M; ++ i)
for (j = 0; j < N; ++ j) {
B[i][j] = A[i][j];
if (com[i] == 1)
B[i][j] = -B[i][j];
}
for (j = 0; j < N; ++ j) {
ysum = nsum = 0;
for (i = 0; i < M; ++ i) {
ysum -= B[i][j];
nsum += B[i][j];
}
if (ysum > nsum)
sum += ysum;
else sum += nsum;
}
if (sum > bsum)
bsum = sum;
}
void make_switches(void) {
// comutatoarele le pun in com[]
int i, j,
p2 = (int)pow(2, M); // 2 ^ M pentru ca voi comuta liniile
for (i = 0; i < p2; ++ i) {
for (j = 0; j < M; ++ j)
if (i & (1 << j))
com[j] = 1;
else
com[j] = 0;
check();
}
}
int main(void) {
FILE *in = fopen("flip.in", "r"),
*out = fopen("flip.out", "w");
fscanf(in, "%d %d", &M, &N);
int i, j;
for (i = 0; i < M; ++ i)
for (j = 0; j < N; ++ j)
fscanf(in, "%d", &A[i][j]);
fclose(in);
make_switches();
fprintf(out, "%d\n", bsum);
fclose(out);
return 0;
}