1 /* 2 題意：給你一個n*n的格子，每一個格子都有一個數值！將兩只bishops放在某一個格子上， 3 每一個bishop可以攻擊對角線上的格子（主對角線和者斜對角線），然后會獲得格子上的 4 數值（只能獲取一次）。要求輸出兩個bishops獲取的最大值以及它們所在的位置！ 5 6 7 思路：直接暴力！....不錯的暴力題目！ 8 首先我們都知道每一條主對角線上的橫縱坐標的和相同，每一條副對角線上的橫縱坐標的差相同！ 9 那么我們在輸入的時候就可以將所有對角線上的數值之和求出來了！ 10 11 最后我們發現如果要獲得最大值，那么還有一條就是兩個bishops所在的對角線不能相交在 12 同一個格子上！只要滿足兩個bishops的哼縱坐標之和互為奇偶就可以了！ 13 14 在所有格子中找到橫縱坐標之和為奇數并且獲得對角線上數值最大的格子和橫縱坐標之 15 和為偶數并且獲得對角線上數值最大的格子！ 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];//橫縱坐標之和為i+j的對角線的數值和 38 sumM[i-j+n]+=num[i][j];//橫縱坐標之差為i-j的對角線的數值和 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;//橫縱坐標之和為奇數并且獲得對角線上數值最大的格子 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;//橫縱坐標之和為偶數并且獲得對角線上數值最大的格子 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 }
?
)
