枚举矩形的上边和下边,花费O(n2),把问题转化成一维的最大M子段和,做一个O(n)的DP。

#include <stdio.h>
const int maxint = 2147483647;

int max(int n, int *a)
{
    
int sum = -maxint, b = 0;
    
for (int i = 1; i <= n; i++)
    
{
        
if (b > 0)
            b 
+= a[i];
        
else
            b 
= a[i];
        sum 
>?= b;
    }

    
return sum;
}


int a[101][101];

int maxsum(int n)
{
    
int sum = -maxint, *= new int[n + 1];
    
for (int i = 1; i <= n; i++)
    
{
        
for (int j = 1; j <= n; j++)
            b[j] 
= a[i][j];
        
for (int j = i + 1; j <= n; j++)
        
{
            
for (int k = 1; k <= n; k++)
                b[k] 
+= a[j][k];
            sum 
>?= max(n, b);
        }

    }

    
return sum;
}

int main()
{
    
int n;
    scanf(
"%d"&n);
    
for (int i = 1; i <= n; i++)
        
for (int j = 1; j <= n; j++)
            scanf(
"%d"&a[i][j]);
    printf(
"%d\n", maxsum(n));
    
return 0;
}
posted on 2007-08-26 13:51 Felicia 阅读(990) 评论(6)  编辑 收藏 引用 所属分类: 动态规划
Comments
  • # re: [动态规划]pku1050
    @潘帕斯雄鹰
    Posted @ 2007-08-30 23:16
    大牛天天更新,小菜一定天天过来踩  回复  更多评论   
  • # re: [动态规划]pku1050
    Gchris
    Posted @ 2007-12-07 16:28
    大牛同学,你好!
    为什么你的blog里有 sum >?= max(n, b); 这样的语句,是不是blog系统出错了?  回复  更多评论   
  • # re: [动态规划]pku1050
    Felicia
    Posted @ 2007-12-07 20:07
    我不是大牛。
    blog系统没错,>?=是运算符  回复  更多评论   
  • # re: [动态规划]pku1050
    Gchris
    Posted @ 2007-12-08 23:25
    @Felicia
    可是我把它拷到 VC 里不能运行
      回复  更多评论   
  • # re: [动态规划]pku1050
    Gchris
    Posted @ 2007-12-08 23:28
    >?=
    是什么意思?  回复  更多评论   
  • # re: [动态规划]pku1050
    Felicia
    Posted @ 2007-12-10 21:23
    ……不要用VC编译,用G++编译  回复  更多评论   

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