題目描述

為了更好的備戰NOIP2013，電腦組的幾個女孩子LYQ,ZSC,ZHQ認為，我們不光需要機房，我們還需要運動，于是就決定找校長申請一塊電腦組的課余運動場地，聽說她們都是電腦組的高手，校長沒有馬上答應他們，而是先給她們出了一道數學題，并且告訴她們：你們能獲得的運動場地的面積就是你們能找到的這個最大的數字。

校長先給他們一個N*N矩陣。要求矩陣中最大加權矩形，即矩陣的每一個元素都有一權值，權值定義在整數集上。從中找一矩形，矩形大小無限制，是其中包含的所有元素的和最大 。矩陣的每個元素屬于[-127,127],例如

0 –2 –7 0
9 2 –6 2
-4 1 –4 1
-1 8 0 –2

在左下角：

9 2
-4 1
-1 8

和為15。

幾個女孩子有點犯難了，于是就找到了電腦組精打細算的HZH，TZY小朋友幫忙計算，但是遺憾的是他們的答案都不一樣，涉及土地的事情我們可不能含糊，你能幫忙計算出校長所給的矩形中加權和最大的矩形嗎？
輸入格式

第一行：n，接下來是n行n列的矩陣。
輸出格式

最大矩形（子矩陣）的和。
輸入輸出樣例
輸入 #1

4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

輸出 #1

15

說明/提示

n<=120

#include <iostream> #include <algorithm> #include <cstring> using namespace std;const int maxn = 1e3 + 10; int a[maxn][maxn]; int sum[maxn][maxn];//左上角為(1, 1)， 右下角為(i, j)的矩形加權和 int n;void init() {for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];}} }int main() {cin >> n;for(int i = 1; i <= n;i++)for(int j = 1; j <= n; j++)cin >> a[i][j];init(); // for(int i= 1; i <= n; i++) { // for(int j= 1; j <= n; j++) // cout << sum[i][j] << " "; // cout << endl; // }long long ans = 0;for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {for(int x = i; x <= n; x++) {for(int y = j; y <= n; y++) {ans = max(ans, 1ll *sum[x][y] - sum[i - 1][y] - sum[x][j - 1] + sum[i - 1][j - 1]);}}}} cout << ans << endl;return 0; }

總結

以上是生活随笔為你收集整理的P1719 最大加权矩形【前缀和】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。