Codeforces 463C Gargari and Bishops(貪心)

題目連結：Codeforces 463C Gargari and Bishops

題目大意：在一個n∗n的國際象棋的棋盤上放兩個主教，要求不能有位置同時被兩個主教攻擊到，然後被一個主教攻擊到的位置上獲得得分。求得分的最大值。

解題思路：黑白格分開考慮最大值,注意全0的時候。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define add(a,b) ((a)+(b))
#define del(a,b) ((a)-(b)+2000)

const int maxn = ;
typedef long long ll;

int n;
ll g[maxn][maxn], l[maxn*], r[maxn*];

int main () {
    scanf("%d", &n);
    memset(l, , sizeof(l));
    memset(r, , sizeof(r));

    for (int i = ; i <= n; i++)
        for (int j = ; j <= n; j++) {
            scanf("%lld\n", &g[i][j]);
            l[add(i, j)] += g[i][j];
            r[del(i, j)] += g[i][j];
        }

    int odd_x, odd_y, even_x, even_y;
    ll max_odd = -, max_even = -;

    for (int i = ; i <= n; i++) {
        for (int j = ; j <= n; j++) {
            if ((i+j)&) {
                if (max_odd < l[add(i, j)] + r[del(i, j)] - g[i][j]) {
                    max_odd = l[add(i, j)] + r[del(i, j)] - g[i][j];
                    odd_x = i;
                    odd_y = j;
                }
            } else {
                if (max_even < l[add(i, j)] + r[del(i, j)] - g[i][j]) {
                    max_even = l[add(i, j)] + r[del(i, j)] - g[i][j];
                    even_x = i;
                    even_y = j;
                }
            }
        }
    }
    printf("%lld\n%d %d %d %d\n", max_even + max_odd, odd_x, odd_y, even_x, even_y);
    return ;
}