acwing3763 数字矩阵 每日一题

题目描述

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

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

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

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

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

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

输入格式

T组输入，给定n,m；表示n*m的矩阵

输出格式

输出最大值

样例描述：

2
2 2
-1 1
1 1
3 4
0 -1 -2 -3
-1 -2 -3 -4
-2 -3 -4 -5

思路：

开始我的想法是盲猜所有的负数都可以转变成正数，对比样例发现，这种情况只有在，负数为偶数的时候才可以全部变成负数，而奇数的时候，可以看成是偶数+1，所以至少最后都还有一个负数，要让和最大，就让绝对值最小的那个为负数即可。

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int g[N][N];
int main(){
    int  t;cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        long long ans=0;
        int a,b=0,minn=1e9;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>g[i][j];
                ans+=abs(g[i][j]);
                minn=min(minn,abs(g[i][j]));
                if(g[i][j]<=0) b++;
            }
        }
        if(b&1) cout<<ans-minn*2<<endl;
        else cout<<ans<<endl;
    }
}