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

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>
            免费看的黄色欧美网站| 韩日精品在线| 国产视频在线观看一区二区三区| 国产精品一区三区| 国产午夜亚洲精品羞羞网站| 亚洲午夜激情网页| 亚洲午夜免费福利视频| 亚洲午夜高清视频| 夜夜嗨av色综合久久久综合网| 中日韩视频在线观看| 国产精品麻豆成人av电影艾秋| 西西人体一区二区| 国产一区香蕉久久| 亚洲人成亚洲人成在线观看图片| 欧美激情视频免费观看| 亚洲免费一级电影| 久久久久久久欧美精品| 99视频精品| 欧美亚洲综合另类| 亚洲免费观看| 久久国产成人| 99精品国产福利在线观看免费| 亚洲曰本av电影| 亚洲日本黄色| 欧美影院成人| 亚洲影视在线| 欧美高清视频在线播放| 久久久亚洲国产天美传媒修理工 | 亚洲私拍自拍| 久久精品国产欧美激情| 在线视频日韩| 久久嫩草精品久久久精品| 亚洲一区免费网站| 欧美jizzhd精品欧美喷水| 久久精品二区| 欧美性大战久久久久| 欧美电影电视剧在线观看| 国产伦精品一区二区三区在线观看| 亚洲国产黄色片| 狠狠久久亚洲欧美| 亚洲在线观看视频| 亚洲天堂av电影| 欧美成人综合网站| 美女图片一区二区| 国产自产在线视频一区| 国产精品99久久不卡二区| 一区二区三区久久网| 欧美a级片网站| 欧美成人精品在线观看| 国产亚洲欧洲| 欧美一二区视频| 欧美专区第一页| 国产欧美激情| 亚洲欧美不卡| 久久99在线观看| 国产区欧美区日韩区| 亚洲性视频网站| 午夜天堂精品久久久久| 国产精品久久久久久久久久久久久久 | 性做久久久久久| 国产精品久久久久久影院8一贰佰| 亚洲国产精品毛片| 亚洲免费成人av电影| 欧美激情第10页| 日韩视频国产视频| 亚洲视频在线观看三级| 欧美午夜三级| 亚洲自拍偷拍网址| 久久精品视频在线看| 国产香蕉久久精品综合网| 久久av红桃一区二区小说| 美女91精品| 亚洲美女性视频| 欧美日韩国产123| 1769国内精品视频在线播放| 久久麻豆一区二区| 亚洲国产色一区| 亚洲一级电影| 国产在线一区二区三区四区| 久久综合色播五月| 99国产欧美久久久精品| 亚洲欧美日本伦理| 国产一区欧美| 欧美国产精品va在线观看| 99国产一区| 久久精品国产一区二区三区免费看| 国内精品久久久久久久影视蜜臀| 久久久久久久久久久久久久一区 | 久久综合伊人77777蜜臀| 亚洲国产日日夜夜| 国产精品久久久久久久久久免费 | 国产午夜精品理论片a级探花| 久久gogo国模裸体人体| 亚洲国产精品第一区二区| 午夜久久tv| 最新中文字幕亚洲| 国产精品入口尤物| 欧美大色视频| 先锋影音国产精品| 亚洲精品久久| 久久性天堂网| 亚洲免费在线精品一区| 亚洲国产成人高清精品| 国产精品女人网站| 欧美激情黄色片| 久久久7777| 一区二区三区毛片| 亚洲成人在线免费| 亚洲一区二区三区乱码aⅴ| 黄色成人av网站| 国产精品每日更新在线播放网址| 久久久亚洲高清| 亚洲欧美综合另类中字| 亚洲剧情一区二区| 欧美福利视频| 久久亚洲国产精品日日av夜夜| 中国成人在线视频| 最近中文字幕日韩精品 | 欧美日韩和欧美的一区二区| 久久视频一区二区| 欧美亚洲一区二区在线观看| 日韩视频免费| 91久久线看在观草草青青| 久久视频在线视频| 久久精品国产免费看久久精品| 亚洲图片欧洲图片日韩av| 亚洲人成免费| 亚洲日本成人女熟在线观看| 国产综合色精品一区二区三区| 国产精品乱码一区二三区小蝌蚪| 欧美.日韩.国产.一区.二区| 久久精品国产一区二区三| 小黄鸭精品aⅴ导航网站入口| 亚洲视频专区在线| 一区二区三区国产在线| 99精品国产高清一区二区| 黑人极品videos精品欧美裸| 国产精品视屏| 国产亚洲欧美激情| 国产在线麻豆精品观看| 国产日韩三区| 狠狠色综合播放一区二区| 国产综合网站| 激情五月婷婷综合| 亚洲第一毛片| 亚洲日本欧美日韩高观看| 亚洲理论在线观看| 在线午夜精品自拍| 亚洲专区在线视频| 欧美自拍偷拍午夜视频| 久久人人看视频| 欧美激情一区二区三区成人| 亚洲激情电影在线| 一区二区三区精品视频| 午夜精品久久久久久久久久久久| 亚洲欧美区自拍先锋| 久久久福利视频| 欧美国产一区二区在线观看 | 久久久不卡网国产精品一区| 久久综合久久久| 欧美日韩精品一区二区在线播放| 国产精品电影网站| 精品动漫3d一区二区三区免费| 亚洲高清资源| 亚洲午夜一区二区三区| 久久国产精彩视频| 亚洲高清久久| 亚洲在线一区二区| 老司机精品视频网站| 欧美视频福利| 伊人久久婷婷| 亚洲永久免费观看| 免费看黄裸体一级大秀欧美| 日韩视频―中文字幕| 久久成人综合视频| 欧美日韩国产成人在线免费| 国产欧美日韩专区发布| 亚洲精品一区中文| 久久精品国产99国产精品| 亚洲国产一区二区三区a毛片 | 免播放器亚洲| 亚洲性视频网站| 欧美成人激情在线| 国产视频一区在线观看| 亚洲精品色图| 老司机午夜精品视频在线观看| 亚洲精品日产精品乱码不卡| 久久精品在线播放| 国产精品区免费视频| 99re成人精品视频| 欧美va亚洲va国产综合| 亚洲一区免费视频| 欧美精品在线一区| 亚洲国产一区二区在线| 久久天天躁狠狠躁夜夜爽蜜月 | 亚洲电影在线看| 久久久国产精品一区| 国产区日韩欧美| 午夜国产精品影院在线观看| 亚洲人成人一区二区在线观看|