Pagini recente » Cod sursa (job #2603366) | Cod sursa (job #666909) | Cod sursa (job #2492835) | Cod sursa (job #1338908) | Cod sursa (job #2323875)
#include <fstream>
#include <vector>
#include <math.h>
typedef std::vector<std::vector<int> > Matrix;
void read(const char* fileName, Matrix& table, int& n, int& m) {
std::ifstream fin(fileName);
fin >> n >> m;
table.resize(n);
for (int i = 0; i < n; ++i) {
table[i].resize(m);
for (int j = 0; j < m; ++j) {
fin >> table[i][j];
}
}
fin.close();
}
int getSum(const Matrix& table, const std::vector<bool>& flip) {
int totalSum = 0;
for (int i = 0; i < table[0].size(); ++i) {
int s = 0;
for (int j = 0; j < table.size(); ++j) {
if (flip[j]) {
s += (-table[j][i]);
} else {
s += table[j][i];
}
}
totalSum += abs(s);
}
return totalSum;
}
void backtracking(int k, const Matrix& table, std::vector<int>& nextStep, std::vector<bool>& flip, int& totalSum) {
int n = table.size();
for (int i = nextStep[k]; i < n; ++i) {
nextStep[k+1] = i + 1;
flip[i] = true;
int s = getSum(table, flip);
if (s > totalSum) {
totalSum = s;
}
backtracking(k + 1, table, nextStep, flip, totalSum);
flip[i] = false;
}
}
int main()
{
Matrix table;
int n, m;
read("flip.in", table, n, m);
std::vector<int> nextStep(n+1, 0);
std::vector<bool> flip(n, false);
int totalSum = 0;
backtracking(0, table, nextStep, flip, totalSum);
std::ofstream fout("flip.out");
fout << totalSum << "\n";
fout.close();
return 0;
}