CodeForces463C Gargari and Bishops(贪心)

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; }

转载于:https://www.cnblogs.com/bhlsheji/p/5271467.html

相关资源：数据结构—成绩单生成器