题目描述 给你一个棋盘 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; }