主題

[OJ練習(xí)] 1124、108 瘋狂一周之後的練習(xí)

テリ君(桃夫模式) | 2022-12-19 11:31:09 | 巴幣 0 | 人氣 130

※耍廢了一週，因為PoE新的一季※

所以我回來了，還好腦袋應(yīng)該沒變差，不過天氣也冷到低於我的活性溫度15度了呢...腦袋轉(zhuǎn)起來RRR

1124(1/5)

就複製貼上的概念= =

#include <stdio.h>

int main(){
    char line[512];

    while(fgets(line, 512, stdin)){
        puts(line);
    }

    return 0;
}

108(3/5)

請問問ChatGPT算作弊ㄇ，因為這題對剛瘋狂完的腦袋來說花了一些時間理解= =

#include <stdio.h>

#define MAX_N 105
#define INT_MIN (-2147483647 - 1)

int matrix[MAX_N][MAX_N];
int prefix_sum[MAX_N][MAX_N];

int main() {
  int n;
  scanf("%d", &n);

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      scanf("%d", &matrix[i][j]);
    }
  }

  // Calculate prefix sum of the matrix
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      prefix_sum[i][j] = prefix_sum[i][j - 1] + matrix[i][j];
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      prefix_sum[i][j] += prefix_sum[i - 1][j];
    }
  }

  // Find the maximal sub-rectangle
  int max_sum = INT_MIN;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      for (int k = i; k <= n; k++) {
        for (int l = j; l <= n; l++) {
          int sum = prefix_sum[k][l] - prefix_sum[i - 1][l] - prefix_sum[k][j - 1] + prefix_sum[i - 1][j - 1];
          if (sum > max_sum) {
            max_sum = sum;
          }
        }
      }
    }
  }

  printf("%d\n", max_sum);

  return 0;
}

主要是要找任意輸入的二維陣列內(nèi)不管正負數(shù)一個小範(fàn)圍內(nèi)加總最大值，所以要慢慢把scale增大去把所有數(shù)字加總，再比較前者加總是否誰比較大，最後輸出最大加總值。