Flip, найти максимальную сумму матрицы путем умножения линий и столбиков на Опции

[DarkWishmaster]

Привет. Вот интересная задача:
Дана матрица NxM где её элементы положитнльные и отрицательные числа. Можно умножить сколько раз угодно любую линию и любой столбик на -1. Найдите максимальную суму чисел из матрицы которая может получиться путем этих умножений.
Например:
5 3
4 -2 2
3 -1 5
2 0 -3
4 1 -3
5 -3 2
Умножаем 3 линию и 2 столбик. Сума=28.
Есть идеи как это вообще сделать?
Сначала я думал что можно пройтись по линиям и столбикам и если по модулю сума отрицательных чисел больше положительных то умножаем на -1, но такой способ не помогает так как когда мы умножаем линию то изменются и колоны и наоборот.

[TarasBer]

Я тут подумал немного.

1. Если разешить переворачивать только столбцы, то задача становится тривиальной - надо просто перевернуть все столбцы с отрицательной суммой.

2. Мы можем для каждой комбинации переворотов строк применить задачу из п.1. Таким образом, время сокращается с O(2^(n+m)) до O((2^n) *m*n).

Что ещё можно сделать, я пока не знаю.

[DarkWishmaster]

IUknown,
Вообщем твое решение дает 20 баллов из 100 ( там тесты онлайн я их не видел ), нашел одно решение (100/100), вроде он тут только по столбикам идет. Эту строку пока не пойму:

 if i and (1 shl (j-1))>0

 Program p1;
var  a : array[1..100,1..100] of longint;
n,m,max : longint;

 
 
Procedure ReaData;
var fin : text;
i,j : integer;
begin
assign(fin,'flip.in');
reset(fin);
readln(fin,n,m);
for i:=1 to n do
for j:=1 to m do
read(fin,a[i,j]);
close(fin);
end;
 
 
Procedure CheckMax;
var s,i,j,t,k : longint;
fout : text;
 begin
    for i:=1 to (1 shl m) do
        begin
           s:=0;
           for k:=1 to n do
              begin
                 t:=0;
                 for j:=1 to m do
                 if i and (1 shl (j-1))>0 then t:=t-a[k,j] else
                 t:=t+a[k,j];
                 if t<-t then s:=s-t else s:=s+t;
              end;
          if s>max then max:=s;
        end;
assign(fout,'flip.out');
rewrite(fout);
writeln(fout,max);
close(fout);
end;
 
begin
ReadData;
CheckMax;
end.

Сообщение отредактировано: DarkWishmaster - 5.07.2011 13:40