CodeForces463C Gargari and Bishops(贪心)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了CodeForces463C Gargari and Bishops(贪心),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1272字,纯文字阅读大概需要2分钟。
内容图文
CodeForces463C Gargari and Bishops(贪心)
题目大意:
在国际象棋的棋盘上放两个主教,这个两个主教不能攻击到同一个格子,最后的得分是这两个主教的攻击的格子上的分数之和。
求最大的分数。
解题思路:
由于攻击的范围是对角线,所以两个主教一个在黑格,一个在白格。画个图就能够发现一旦一个主教放在了黑格。那么剩下的黑格是都不能在放主教的,否则就是攻击到同样的格子。
所以求出每条对角线的和,通过这个得出每一个格子作为主教的得分,最后黑白格分开讨论。
代码:
#include <cstdio>
#include <algorithm>
#include <cstring>
using
namespace
std;
typedeflonglong ll;
constint maxn = 2e3 + 5;
int N;
ll G[maxn][maxn];
ll d1[maxn*2], d2[maxn*2];
intmain(){
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);
}
return0;
}
原文:http://www.cnblogs.com/bhlsheji/p/5271467.html
内容总结
以上是互联网集市为您收集整理的CodeForces463C Gargari and Bishops(贪心)全部内容,希望文章能够帮你解决CodeForces463C Gargari and Bishops(贪心)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。