1 /* 2 題意：給你一個(gè)n*n的格子，每一個(gè)格子都有一個(gè)數(shù)值！將兩只bishops放在某一個(gè)格子上， 3 每一個(gè)bishop可以攻擊對(duì)角線(xiàn)上的格子（主對(duì)角線(xiàn)和者斜對(duì)角線(xiàn)），然后會(huì)獲得格子上的 4 數(shù)值（只能獲取一次）。要求輸出兩個(gè)bishops獲取的最大值以及它們所在的位置！ 5 6 7 思路：直接暴力！....不錯(cuò)的暴力題目！ 8 首先我們都知道每一條主對(duì)角線(xiàn)上的橫縱坐標(biāo)的和相同，每一條副對(duì)角線(xiàn)上的橫縱坐標(biāo)的差相同！ 9 那么我們?cè)谳斎氲臅r(shí)候就可以將所有對(duì)角線(xiàn)上的數(shù)值之和求出來(lái)了！ 10 11 最后我們發(fā)現(xiàn)如果要獲得最大值，那么還有一條就是兩個(gè)bishops所在的對(duì)角線(xiàn)不能相交在 12 同一個(gè)格子上！只要滿(mǎn)足兩個(gè)bishops的哼縱坐標(biāo)之和互為奇偶就可以了！ 13 14 在所有格子中找到橫縱坐標(biāo)之和為奇數(shù)并且獲得對(duì)角線(xiàn)上數(shù)值最大的格子和橫縱坐標(biāo)之 15 和為偶數(shù)并且獲得對(duì)角線(xiàn)上數(shù)值最大的格子！ 16 二者最大獲得值相加就是最終的答案了！ 17 */ 18 #include<iostream> 19 #include<cstring> 20 #include<cstdio> 21 #include<algorithm> 22 #define N 2005 23 using namespace std; 24 typedef long long LL; 25 int num[N][N]; 26 LL sumN[N*2], sumM[N*2]; 27 28 int n; 29 30 int main(){ 31 while(scanf("%d", &n)!=EOF){ 32 memset(sumN, 0, sizeof(sumN)); 33 memset(sumM, 0, sizeof(sumM)); 34 for(int i=1; i<=n; ++i) 35 for(int j=1; j<=n; ++j){ 36 scanf("%d", &num[i][j]); 37 sumN[i+j]+=num[i][j];//橫縱坐標(biāo)之和為i+j的對(duì)角線(xiàn)的數(shù)值和 38 sumM[i-j+n]+=num[i][j];//橫縱坐標(biāo)之差為i-j的對(duì)角線(xiàn)的數(shù)值和 39 } 40 41 LL maxOdd=-1, maxEvent=-1, s; 42 int x1, x2, y1, y2; 43 for(int i=1; i<=n; ++i) 44 for(int j=1; j<=n; ++j){ 45 if((i+j)&1){ 46 if(maxOdd<(s=sumN[i+j]+sumM[i-j+n]-num[i][j])){ 47 maxOdd=s;//橫縱坐標(biāo)之和為奇數(shù)并且獲得對(duì)角線(xiàn)上數(shù)值最大的格子 48 x1=i; 49 y1=j; 50 } 51 } 52 else{ 53 if(maxEvent<(s=sumN[i+j]+sumM[i-j+n]-num[i][j])){ 54 maxEvent=s;//橫縱坐標(biāo)之和為偶數(shù)并且獲得對(duì)角線(xiàn)上數(shù)值最大的格子 55 x2=i; 56 y2=j; 57 } 58 } 59 } 60 61 printf("%lld\n",maxOdd+maxEvent); 62 printf("%d %d %d %d\n", x1, y1, x2, y2); 63 } 64 return 0; 65 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/hujunzheng/p/3946876.html

總結(jié)

以上是生活随笔為你收集整理的codeforces Gargari and Bishops（很好的暴力）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。