codeforces Gargari and Bishops(很好的暴力)
2024-09-13 07:06:31
/*
题意:给你一个n*n的格子,每一个格子都有一个数值!将两只bishops放在某一个格子上,
每一个bishop可以攻击对角线上的格子(主对角线和者斜对角线),然后会获得格子上的
数值(只能获取一次)。要求输出两个bishops获取的最大值以及它们所在的位置! 思路:直接暴力!....不错的暴力题目!
首先我们都知道每一条主对角线上的横纵坐标的和相同,每一条副对角线上的横纵坐标的差相同!
那么我们在输入的时候就可以将所有对角线上的数值之和求出来了! 最后我们发现如果要获得最大值,那么还有一条就是两个bishops所在的对角线不能相交在
同一个格子上!只要满足两个bishops的哼纵坐标之和互为奇偶就可以了! 在所有格子中找到横纵坐标之和为奇数并且获得对角线上数值最大的格子和横纵坐标之
和为偶数并且获得对角线上数值最大的格子!
二者最大获得值相加就是最终的答案了!
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N 2005
using namespace std;
typedef long long LL;
int num[N][N];
LL sumN[N*], sumM[N*]; int n; int main(){
while(scanf("%d", &n)!=EOF){
memset(sumN, , sizeof(sumN));
memset(sumM, , sizeof(sumM));
for(int i=; i<=n; ++i)
for(int j=; j<=n; ++j){
scanf("%d", &num[i][j]);
sumN[i+j]+=num[i][j];//横纵坐标之和为i+j的对角线的数值和
sumM[i-j+n]+=num[i][j];//横纵坐标之差为i-j的对角线的数值和
} LL maxOdd=-, maxEvent=-, s;
int x1, x2, y1, y2;
for(int i=; i<=n; ++i)
for(int j=; j<=n; ++j){
if((i+j)&){
if(maxOdd<(s=sumN[i+j]+sumM[i-j+n]-num[i][j])){
maxOdd=s;//横纵坐标之和为奇数并且获得对角线上数值最大的格子
x1=i;
y1=j;
}
}
else{
if(maxEvent<(s=sumN[i+j]+sumM[i-j+n]-num[i][j])){
maxEvent=s;//横纵坐标之和为偶数并且获得对角线上数值最大的格子
x2=i;
y2=j;
}
}
} printf("%lld\n",maxOdd+maxEvent);
printf("%d %d %d %d\n", x1, y1, x2, y2);
}
return ;
}
最新文章
- Oozie命令行常用命令汇总[转]
- 利用jquery和flash实现复制文字功能(等同于ctrl+c)
- OpenMesh 删除网格顶点
- maya,mel,eval,stringarray
- 在数学建模中学MATLAB
- 微信公众平台开发(112) 自动更新微信access token
- Java NIO学习(一)
- 事务——sql server中的事务应用举例
- javascript学习-原生javascript的小特效(原生javascript实现链式运动)
- poj 3034 动态规划
- Ajax 技术二
- Activity的活动周期
- sphinx的简单实例
- htmlparser 精确提取的一些代码
- 月見(つきみ) 夕(ゆう) SumiHui.墨虺
- thinkphp中使用PHPEXCEL导出数据
- OC - 16.大文件下载
- TopCoder SRM 566 Div 1 - Problem 1000 FencingPenguins
- linux(centos 7)学习之 ~目录下的文件anaconda-ks.cfg
- [Windows]查看运行进程的参数【wmic】
热门文章
- linux下subversion server安装手册
- delayed ack与nagle&#39;s算法
- eclipse tomcat集成开发,修改server.xml
- leetcode Insertion Sort List
- C++的四种cast操作符的区别--类型转换(转)
- ansible 自动化(3)
- Hadoop伪分布搭建
- Revert R12.1.3 Homepage Layout to Link Style as in R12.1.1 or 11i
- [leetcode 48] rotate image
- codeblocks配置GLUT