poj 1050-最大サブシーケンスと

15805 ワード

http://acm.pku.edu.cn/JudgeOnline/problem?id=1050
                                                                                    
         To the Max
Time Limit: 1000MS
Memory Limit: 10000K
Total Submissions: 21973
Accepted: 11400
Description
Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1*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 * 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
40 -2 -7 0 9 2 -6 2-4 1 -4  1 -18  0 -2

Sample Output
15

hdu 1003とは異なる問題ですが、1003と同じ考えで、具体的なコードは以下の通りです.


コード#コード#

   
     
1 #include < stdio.h >
2 #include < stdlib.h >
3 #include < string .h >
4   int n,a[ 101 ][ 101 ];
5   int s[ 101 ];
6 int ma( int * p){ ————
7 int i,max =- ( 1 << 30 ),b;
8 b = p[ 1 ];
9 for (i = 2 ;i <= n;i ++ )
10 {
11 if (b < 0 )b = p[i];
12 else b = b + p[i];
13 if (max < b)max = b;
14 }
15 return max;
16 }
17
18 int main(){
19 int i,j,l,k,max =- ( 1 << 30 ),t;
20 scanf( " %d " , & n);
21 for (i = 1 ;i <= n;i ++ )
22 for (j = 1 ;j <= n;j ++ )
23 scanf( " %d " , & a[i][j]);
24 memset(s, 0 , sizeof (s));
25 for (l = 1 ;l <= n;l ++ ) —————
26 for (i = 1 ;i <= n;i ++ )——————
27 { for (j = i;j <= l;j ++ )
28 for (k = 1 ;k <= n;k ++ )
29 s[k] += a[j][k];——————s[k] k i l
30 t = ma(s);
31 if (max < t)max = t;
32 memset(s, 0 , sizeof (s));
33 }
34 printf( " %d
" ,max);
35 return 0 ;
36 }

経験の総括:プログラミングの過程の中で、未知を既知の数学の思考に変えることに注意します. 
本題は行列であるが,それを一列数に変換してから最大のサブシーケンス和を求めることを考えている.しかし、どのように転化しますか?
7 -8 9
-4 5 6
1 2 -3
主に同じ列の数をマージします.たとえば、1行目から2行目の最後まで、各列の和からなるシーケンスは次のようになります.
3 -3 15
次に、このシーケンスの最大サブシーケンスとを求めます.求めてmaxと比較すると,最後に出力されるのは必ず最大行列和である.
プログラム内で初期位置と終了位置で列挙するほか、各列の要素個数と開始位置書き込みループを列挙することもできます.