CodeForces463C Gargari and Bishops(贪心)

CodeForces463C

题目大意： 

在国际象棋的棋盘上放两个主教，这个两个主教不能攻击到同一个格子，最后的得分是这两个主教的攻击的格子上的分数之和。

求最大的分数。

解题思路： 

由于攻击的范围是对角线，所以两个主教一个在黑格，一个在白格。画个图就能够发现一旦一个主教放在了黑格。那么剩下的黑格是都不能在放主教的，否则就是攻击到同样的格子。

所以求出每条对角线的和，通过这个得出每一个格子作为主教的得分，最后黑白格分开讨论。

代码：

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

typedef long long ll;

const int maxn = 2e3 + 5;

int N;

ll G[maxn][maxn];

ll d1[maxn*2], d2[maxn*2];

int main () {

    while (scanf ("%d", &N) != EOF) {

        memset(d1, 0, sizeof (d1));

        memset(d2, 0, sizeof (d2));

        for (int i = 1; i <= N; i++)

            for (int j = 1; j <= N; j++) {

                scanf ("%lld", &G[i][j]);

                d1[i + j] += G[i][j];

                d2[(i - j) + N] += G[i][j];

            }

        ll odd = -1, even = -1;

        int oddx, oddy, evenx, eveny;

        for (int i = 1; i <= N; i++) {

            for (int j = 1; j <= N; j++) {

                if ((i + j)&1) {

                    if (odd < d1[i + j] + d2[i - j + N] - G[i][j]) {

                        odd = d1[i + j] + d2[i - j + N] - G[i][j];

                        oddx = i;

                        oddy = j;

                    }

                } else {

                    if (even < d1[i + j] + d2[i - j + N] - G[i][j]) {

                        even = d1[i + j] + d2[i - j + N] - G[i][j];

                        evenx = i;

                        eveny = j;

                    }

                }

            }

        }

        printf ("%lld\n%d %d %d %d\n", odd + even, oddx, oddy, evenx, eveny);

    }

    return 0;

}