首页 > 代码库 > Codeforces 463C. Gargari and Bishops
Codeforces 463C. Gargari and Bishops
题目大意：
给出一个n*n的棋盘，要在这个棋盘上放两个象（能将以自己为中心的两条斜对角线上的子全部吃掉），要求两个象不能吃到相同的子，问最后最大能够吃到的价值，和需要在哪两个点上放置这两个象。
做法:
首先我们需要知道在每个点上防置象能吃到多少，怎么解决这个问题？我们可以将左斜方向和右斜方向的每一行编号，然后分别计算出每一行的价值，最后将每个点对应的左斜右斜的伤害加起来再减掉当前点的价值。这其中的转化应该很好弄出来。
既然我们现在得到了这样一个数组，那么接下来，只需要找出两个不会吃到相同子的位置，并且能够吃到最大的价值。
观察发现（当然这个是通过一些数学公式推导出来的，两条直线相交，点坐标为整数这说明有交点），只要两个点的横坐标纵坐标相加奇偶性不同即可，那么我们只需要找出坐标相加为奇数的点的最大价值，在加上坐标相加为偶数的点的最大价值，两个值相加就能得到最后的答案。
代码：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#define pb push_back
using namespace std;
const long long NN=4001111;
long long f[2222][2222];
long long s1[4004];
long long s2[4004];
struct P{
long long v;
int i,j;
}sum[NN];
bool cmp(P s1,P s2){
return s1.v>s2.v;
}
int main(){
long long n;cin>>n;
for(long long i=1;i<=n;i++)
for(long long j=1;j<=n;j++){
//cin>>f[i][j];
scanf("%I64d",&f[i][j]);
s1[i+j-1]+=f[i][j];
s2[n+1-j+i-1]+=f[i][j];
}
for(long long i=1;i<=n;i++)
for(long long j=1;j<=n;j++){
long long id=(i-1)*n+j;
sum[id].v=s1[i+j-1]+s2[n+1-j+i-1]-f[i][j];
sum[id].i=i;
sum[id].j=j;
}
long long ans1=-1,ans2=-1;
long long ansx1=0,ansy1=0,ansx2=0,ansy2=0;
for(long long i=1;i<=n*n;i++)
{
if((abs(sum[i].i+sum[i].j)&1)&&ans1<sum[i].v)
{
ans1=sum[i].v;
ansx1=sum[i].i,ansy1=sum[i].j;
}
if(!(abs(sum[i].i+sum[i].j)&1) && ans2<sum[i].v)
{
ans2=sum[i].v;
ansx2=sum[i].i,ansy2=sum[i].j;
}
}
cout<<ans1+ans2<<endl;
cout<<ansx1<<' '<<ansy1<<' ';
cout<<ansx2<<' '<<ansy2<<endl;
}Codeforces 463C. Gargari and Bishops
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。