题目描述 给你一个棋盘 n*n 并且让你放两个教主攻击棋盘中的位置x,y a[x][y] 代表攻击后将得到的值 每个教主能攻击对角线上的位置,现在求两个教主不会同时攻击某个位置时获得的最大价值;
分析 : 首先对角线 的处理用到了八皇后的处理方法 即副x+y, 和主x-y ;而两个点不会同时攻击 同一个位置 则(y=x+c)x1+y1!=x2-y2 (副 副 和主主重合容易去掉) 显然当x1+y1和x2-y2奇偶性不一样时肯定不等
(这是自己推出来的,网上说的黑白棋估计就是这个)
因为初始化 和 数据范围 wa了
ac代码:
#include<bits/stdc++.h>
using namespace std;
const int MAX=2e3+3;
int mapp[MAX][MAX];
map<int ,long long > value;
int n;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
pair<int ,int> pp[2];
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
cin>>mapp[i][j];
value[i-j]+=mapp[i][j];
value[i+j+2*n]+=mapp[i][j];
}
long long ans1=0,ans2=0;
pp[0].first=1,pp[0].second=1,pp[1].first=1,pp[1].second=2;//初始化防止判
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if((i+j)%2)if(ans1<value[i+j+2*n]+value[i-j]-mapp[i][j]){
ans1=value[i+j+2*n]+value[i-j]-mapp[i][j];
pp[0]=make_pair(i,j);
}
else ;
else if(ans2<value[i+j+2*n]+value[i-j]-mapp[i][j]){
ans2=value[i+j+2*n]+value[i-j]-mapp[i][j];
pp[1]=make_pair(i,j);
}
else ;
}
int x1=pp[0].first,y1=pp[0].second,x2=pp[1].first,y2=pp[1].second;
cout<<ans1+ans2<<endl;
cout<<x1<<' '<<y1<<' '<<x2<<' '<<y2<<endl;
}

京公网安备 11010502036488号