题目描述

给定一个 n×m 的整数矩阵，其中第 i 行第 j 列的元素为 aij。

你可以进行任意多次如下操作：

选择矩阵中的两个相邻元素，将它们均乘以 −1。

同一个元素可以被选中多次。

你需要通过上述操作，使得矩阵中所有元素的和尽可能大。

计算并输出这个和的最大可能值。

输入格式
第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含两个整数 n,m。

接下来 n 行，每行包含 m 个整数，表示整个矩阵，其中第 i 行第 j 列的数为 aij。

输出格式
每组数据输出一行结果，表示矩阵的所有元素的最大可能和。

数据范围
1≤T≤100,
2≤n,m≤10,
−100≤aij≤100

样例

输入样例：
2
2 2
-1 1
1 1
3 4
0 -1 -2 -3
-1 -2 -3 -4
-2 -3 -4 -5
输出样例：
2
30

算法1

重点：可以通过若干次操作改变矩阵中任何两点的值，而其他的点不变
所以：如果负数的个数为偶数的话，可以通过若干次操作，该负数都能变成正数，所以这种情况下的 和就是所有数的绝对值之和。

如果负数个数为奇数的话，那么经过若干次操作，该矩阵中至少存在一个负数，因为只能两两修改。
所以 只用找到矩阵中绝对值最小的数即可，将它变为负数，而其他的都可以变成正数。

答案就是 所有数之和-2*该绝对值最小的数。
（因为所有数之和 加上了该绝对值 本来应该减去，所以要减去两倍）

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
    int T;
    cin>>T;
    while(T--){
        int n,m;
        int sum=0;//所有数的绝对值之和 
        int minx=1e8;//取绝对值最小的数，先把最小值设为一个大值。 
        int cnt=0;//负数的个数 
        cin>>n>>m;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++)
            {
                int x;
                cin>>x;
                if(x<0) cnt++;//记录负数个数 
                sum+=abs(x);
                minx=min(minx,abs(x));//找到绝对值最小的数 
            }
        }
        if(cnt%2) cout<<sum-2*minx<<endl;//如果负数的个数为奇数 
        else
        cout<<sum<<endl;//负数个数为偶数 
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla