CF1676D

Mr__Cat · 2022-08-04 20:09:52 · 题解

题目描述

给一个 n \times m 的棋盘，并且 (i,j) 位置上有 q_{i,j} 这样一个数字（非负整数），我们放一个象在上面（国际象棋中的象只走斜线），问最多可取的数字和为多少？

思路

看完题目的第一个想法——枚举，枚举象的位置，并在之前计算好前缀和。当然，要用到 map。最后计算每个点对它所在斜线的贡献好像就可以了！！！

代码

#include<bits/stdc++.h>
using namespace std;
int a[101][101];
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,m,ans=0;;
        cin>>n>>m;
        map<int,int> l,r;
        //(-x)+y可能是负数，这里使用映射
        //如果把每个r的值加上m也可以
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>a[i][j];
                l[i+j]+=a[i][j];
                r[i-j]+=a[i][j];
                //计算前缀和
            }
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                //枚举象的位置
                ans=max(ans,l[i+j]+r[i-j]-a[i][j]);
                //计算贡献，取max
        cout<<ans<<'\n';
    }
}