青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

POJ 1050 To the MAX(最大子矩陣問題)

Problem Description
Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1 x 1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle.

As an example, the maximal sub-rectangle of the array:

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

is in the lower left corner:

9 2
-4 1
-1 8

and has a sum of 15.
 

Input
The input consists of an N x N array of integers. The input begins with a single positive integer N on a line by itself, indicating the size of the square two-dimensional array. This is followed by N 2 integers separated by whitespace (spaces and newlines). These are the N 2 integers of the array, presented in row-major order. That is, all numbers in the first row, left to right, then all numbers in the second row, left to right, etc. N may be as large as 100. The numbers in the array will be in the range [-127,127].
 

Output
Output the sum of the maximal sub-rectangle.
 

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

Sample Output
15
給定一個(gè)N*N的矩陣,要求一個(gè)子矩陣,使得該矩陣的元素和最大。轉(zhuǎn)為為最大連續(xù)子序列問題。
 1 #include <iostream>
 2 
 3 const int N = 101;
 4 const int inf = INT_MIN;
 5 int a[N][N],b[N];
 6 
 7 int MaxSum(int n,int a[]){
 8     int i,sum=inf,b=0;
 9     for(i=1;i<=n;i++){
10         b=(b+a[i])>a[i]?(b+a[i]):a[i];
11         sum=sum>b?sum:b;
12     }
13     return sum;
14 }
15 int main(){
16     int n,i,j,k,max,ans;
17     while(scanf("%d",&n)!=EOF){
18         for(i=1;i<=n;i++)
19             for(j=1;j<=n;j++)
20                 scanf("%d",&a[i][j]);
21         for(max=inf,i=1;i<=n;i++){
22             memset(b,0,sizeof(b));
23             for(j=i;j<=n;j++){
24                 for(k=1;k<=n;k++)
25                     b[k]+=a[j][k];
26                 ans=MaxSum(n,b);
27                 max=max>ans?max:ans;
28             }
29         }
30         printf("%d\n",max);
31     }
32     return 0;
33 }

posted on 2009-04-25 12:30 極限定律 閱讀(1750) 評論(0)  編輯 收藏 引用 所屬分類: ACM/ICPC

<2009年4月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿(10)

隨筆分類

隨筆檔案

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            欧美一区二区在线免费观看| 亚洲人成网在线播放| 亚洲午夜一区二区| 欧美三区在线| 午夜精品一区二区三区电影天堂| 亚洲一区二区三区四区五区午夜| 国产精品久久久久久户外露出| 亚洲在线视频免费观看| 亚洲欧美激情视频| 亚洲第一页中文字幕| 亚洲国产mv| 国产精品久久久久久亚洲调教| 欧美综合国产| 欧美成人福利视频| 亚洲一区二区3| 欧美一区二区三区精品电影| 亚洲三级视频在线观看| 亚洲一区二区在线观看视频| 狠狠色丁香久久婷婷综合_中| 亚洲激情偷拍| 国产视频一区免费看| 欧美肥婆在线| 国产精品自拍在线| 亚洲激情视频在线| 国产亚洲激情在线| 亚洲精品一区中文| 在线成人国产| 亚洲天堂成人| 亚洲精品综合| 久久大逼视频| 亚洲欧美日韩在线不卡| 久久网站免费| 久久成人亚洲| 欧美午夜精品伦理| 欧美激情在线有限公司| 欧美激情在线观看| 精品av久久707| 一区二区三区四区五区在线| 91久久嫩草影院一区二区| 小黄鸭精品aⅴ导航网站入口| aa亚洲婷婷| 玖玖精品视频| 久热爱精品视频线路一| 国产精品亚洲综合一区在线观看| 亚洲国产婷婷综合在线精品| 尤妮丝一区二区裸体视频| 亚洲欧美电影院| 亚洲一区www| 欧美美女视频| 亚洲欧洲另类| 亚洲精品女人| 欧美黑人多人双交| 欧美成人日韩| 在线看视频不卡| 久久精品日产第一区二区三区| 午夜免费日韩视频| 国产精品久久久久久久久婷婷| 亚洲精品日本| 一本一本a久久| 欧美日韩高清区| 亚洲九九九在线观看| 日韩午夜av| 欧美日韩系列| 一区二区国产在线观看| 一区二区三区四区五区视频| 欧美国产一区二区三区激情无套| 亚洲福利视频网站| 亚洲欧洲日产国产综合网| 美女诱惑黄网站一区| 欧美不卡一区| 亚洲伦理一区| 欧美色播在线播放| 亚洲欧美国产va在线影院| 久久九九热re6这里有精品| 国产又爽又黄的激情精品视频 | 午夜精品美女久久久久av福利| 欧美色欧美亚洲另类七区| 日韩西西人体444www| 亚洲一区二区在线| 国产精品一区二区久久久| 欧美中文字幕第一页| 欧美成人高清| 一区二区三区久久| 国产女人18毛片水18精品| 久久精品五月| 亚洲欧洲日本专区| 性做久久久久久久久| 伊伊综合在线| 欧美日韩情趣电影| 欧美综合二区| 亚洲美女在线看| 久久精品免视看| 亚洲经典一区| 国产精品久久久久婷婷| 久久久久女教师免费一区| 亚洲日本一区二区| 欧美一区影院| 夜夜精品视频| 狠狠干综合网| 国产精品久久久久久久久久妞妞| 久久精品人人爽| 一区二区三区精品视频在线观看| 久久久噜噜噜久久中文字免| 亚洲免费av网站| 国产一区二区三区无遮挡| 欧美理论在线播放| 欧美在线免费看| 日韩视频一区二区三区在线播放| 久久精品日产第一区二区三区| 日韩一级不卡| 1000部国产精品成人观看| 国产精品人人爽人人做我的可爱| 欧美成人精品1314www| 欧美在线free| 亚洲一区二区动漫| 亚洲黄一区二区三区| 久热这里只精品99re8久| 亚洲中字黄色| 一区二区三区毛片| 亚洲人久久久| 在线观看久久av| 国内外成人在线| 国产麻豆91精品| 国产精品av久久久久久麻豆网| 欧美黄色影院| 免费欧美网站| 久久综合色一综合色88| 久久激五月天综合精品| 亚洲一区二区在线免费观看| 最新成人av在线| 亚洲风情亚aⅴ在线发布| 欧美成人精精品一区二区频| 久久久久久国产精品mv| 久久精品亚洲一区二区| 欧美在线播放一区| 校园春色综合网| 午夜精品久久久久久久99黑人| 中文国产成人精品| 夜夜嗨av一区二区三区| 亚洲免费电影在线观看| 亚洲美女少妇无套啪啪呻吟| 91久久夜色精品国产九色| 在线观看福利一区| 亚洲激情在线播放| 亚洲另类自拍| 一区二区欧美在线| 亚洲伊人伊色伊影伊综合网| 亚洲一级片在线观看| 亚洲综合好骚| 久久精品噜噜噜成人av农村| 久久频这里精品99香蕉| 欧美高清影院| 亚洲精选中文字幕| 亚洲免费综合| 欧美在线首页| 久久精品日韩一区二区三区| 久久综合影视| 欧美精品一区二区三区很污很色的 | 99精品国产福利在线观看免费| 欧美影视一区| 男男成人高潮片免费网站| 欧美mv日韩mv亚洲| 国产精品高潮呻吟久久av无限 | 亚洲大胆美女视频| 日韩亚洲精品视频| 性久久久久久久| 欧美暴力喷水在线| 亚洲精品在线观看免费| 亚洲私拍自拍| 久热re这里精品视频在线6| 欧美成人精品一区二区| 国产精品户外野外| 黄色av日韩| 亚洲午夜羞羞片| 开心色5月久久精品| 亚洲美女免费精品视频在线观看| 亚洲自拍偷拍一区| 欧美成人国产| 国产在线欧美日韩| 夜夜爽夜夜爽精品视频| 欧美在线在线| 亚洲欧洲精品一区二区三区波多野1战4 | 一本大道久久精品懂色aⅴ| 欧美一区二区视频在线观看2020| 免费在线观看日韩欧美| 在线一区二区日韩| 久久综合狠狠| 国产农村妇女精品| 一区二区三区不卡视频在线观看| 久久精品在线免费观看| 99re66热这里只有精品4| 久久久久免费视频| 国产精品久久久久99| 亚洲精品国产精品国自产在线| 欧美在线关看| 99热这里只有精品8| 欧美99久久| 一区二区三区在线高清| 久久精品免费电影| 亚洲综合色丁香婷婷六月图片|