竹園論壇

標題: Q108 - Maximum Sum [打印本頁]

作者: HSCHE    時間: 2014-4-28 07:54
標題: Q108 - Maximum Sum
本帖最後由 HSCHE 於 2014-5-6 08:14 編輯

給你一個NxN的陣列,請你找出有最大和的子區域(sub-rectangle)其和為多少。一個區域的和指的是該區域中所有元素值的和。一個區域是指相連的任意大小的子陣列。例如,對以下的二維陣列:
其最大和的子區域位於左下角,並且其和為15。如下所示:
Input
只有一組測試資料,第一列有一個正整數N(N <= 100),代表此二維陣列大小為NxN。
從第二列起有N^2個整數,代表此陣列的內容。每個整數都介於-127到127之間,且以列為主(row-major)的順序排列。Sample Input即為上圖所示的陣列。
Output
輸出有最大和的子區域其和是多少。
Sample Input
40 -2 -7  0 9  2 -6  2-4  1 -4  1 -18  0 -2
Sample Output
15

在此附上題目連結UVA:http://uva.onlinejudge.org/external/1/108.htmlLUCKY CAT:http://luckycat.kshs.kh.edu.tw/homework/q108.htm
解題感想:這題主要是考二維陣列,使用的方法是先將二維壓縮成一維,再用一維去運算,只要能壓縮成功,這題就輕鬆GG

AC CODE:
#include<iostream>
  • #include<cstring>
  • #include<cstdio>
  • using namespace std;
  • int main()
  • {
  •         int a[101][101];
  •         long long int h,maxx=0,tot=0;
  •         cin>>h;
  •         for(int i=1;i<=h;i++)
  •         {
  •                 for(int j=1;j<=h;j++)
  •                 {
  •                         cin>>a[i][j];
  •                 }
  •         }
  •         for(int i=1;i<=h;i++)
  •         {
  •                 for(int j=2;j<=h;j++)
  •                 {
  •                         a[i][j]+=a[i][j-1];
  •                 }
  •         }
  •         for(int x=1;x<=h;x++)
  •         {
  •                 for(int x2=x;x2<=h;x2++)
  •                 {
  •                         //cout << "(" << x << "," << x2 << ")" << endl;
  •                         for(int i=1;i<=h;i++)
  •                         {
  •                                 a[i][0]=0;
  •                                 tot+=a[i][x2]-a[i][x-1];
  •                                 
  •                                 //cout << "total : " << tot << endl;
  •                                 
  •                                 if(tot>maxx)
  •                                 {
  •                                         maxx=tot;
  •                                 }
  •                                 if(tot<=0)
  •                                 tot=0;
  •                         }
  •                         tot=0;
  •                 }
  •         }
  •         cout<<maxx<<"\n";
  •         return 0;
  • }








  • 歡迎光臨 竹園論壇 (http://forum.tfcis.org/) Powered by Discuz! X3.2