本文主要是介绍Codeforces 463C Gargari and Bishops，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
在一个n*n的矩阵中，让你选择两个点，使得两点所在的主对角线和斜对角线所包含的元素值之和最大。两点的对角线不能相交于同一个点。
思路：
一开始就被不能相交于同一个点难住了。后来问了铭神，二维矩阵其实是个二分图，就好比黑白染色。
先预处理出两种对角线的和，根据下面两条性质。
主对角线：横纵坐标相减的结果是相等的。
斜对角线：横纵坐标的和是相等的。
横纵坐标的和的奇偶性决定它们的对角线能否相交。
AC代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <vector>
typedef long long ll;
using namespace std;
const int MAXN = 2005;
int a[MAXN][MAXN];
ll lsum[2*MAXN], rsum[2*MAXN];
int n;
int main()
{scanf("%d", &n);for(int i = 1;i <= n; i++)for(int j = 1;j <= n; j++){scanf("%d" ,&a[i][j]);rsum[i-j+n] += a[i][j];lsum[i+j] += a[i][j];}//ll rmax = -1, lmax = -1;int x1, y1, x2, y2;for(int i = 1;i <= n; i++)for(int j = 1;j <= n; j++){ll tmp = rsum[i-j+n] + lsum[i+j] - a[i][j];if((i+j) & 1) //black{if(tmp > rmax){x1 = i, y1 = j;rmax = tmp;}}else{if(tmp > lmax){x2 = i, y2 = j;lmax = tmp;}}}cout<<rmax+lmax<<endl;printf("%d %d %d %d\n",x1, y1, x2, y2);return 0;
}这篇关于Codeforces 463C Gargari and Bishops的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
