pku 1050

 

 1 首先学到的是 求一维数组最大子段和! 这个的想法很简单,只要大家多动几次笔,想想就会理解了!
 2 我卡住的地方是,为什么如果 <= 0 就从新开始 然道 <= 0 这个子段中任意数字重新开始新的子段就没有最大的?
 3 最后想想就明白了!
 4 
 5 int p( int *s2,int c1 )
 6 {
 7  int max = -1000;
 8  int sum = 0;
 9  for ( int i = 0; i != c1; ++i ) // 一维数组 最大 子段和
10  {
11   if ( sum > 0 )
12    sum += s2[i];
13   else sum = s2[i];
14   if ( sum > max )
15    max = sum;
16  }
17 }
18 
19 然后做了到题目,求矩阵的最大子矩阵的和! 它的思想和一维是一样的!
20 
21 #include <cstdio>
22 
23 int p( int *s2,int c1 )
24 {
25  int max = -1000;
26  int sum = 0;
27  for ( int i = 0; i != c1; ++i ) // 一维数组 最大 子段和
28  {
29   if ( sum > 0 )
30    sum += s2[i];
31   else sum = s2[i];
32   if ( sum > max )
33    max = sum;
34  }
35  return max;
36 }
37 
38 int main()
39 {
40  int r,c;
41  scanf ( "%d",&r );
42  int s1[500][500];
43  for ( int i = 0; i != r; ++i )
44   for ( int j = 0; j != r; ++j )
45    scanf ( "%d\n",&s1[i][j] );
46  int b[500];
47  int max = -1000;
48  int max1;
49  for ( int i = 0; i != r; ++i ) //控制起始行
50  {
51   for ( int b1 = 0; b1 != r; ++b1 )
52    b[b1] = 0;
53   for ( int j = i; j != r; ++j ) // 控制行数 从 i 起始 到最后一行; 
54   {
55    for ( int k = 0; k != r; ++k )
56     b[k] += s1[j][k];
57    max1 = p( b,r );
58    if ( max1 > max )
59     max = max1;
60   }
61  }
62  printf ( "%d\n",max );
63  return 0;
64 }
65 
66 

posted on 2010-03-21 21:31 haozi 阅读(281) 评论(0)  编辑 收藏 引用 所属分类: 动态规划


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年6月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

导航

统计

常用链接

留言簿

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜