| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1716 人关注过本帖
标题:再出一题(祭祀广场)
只看楼主 加入收藏
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
呵呵,感谢楼上的指正,可惜这楼不是我打的地基,否则真想给你加两分
修改了笔误及逻辑上的错误,不过没有在代码级做优化,有兴趣你再拿到OJ上去测试一下。
至于计算范围,楼主给的范围只是64 X 64。需要的话改一下两个宏就可以, 这不是问题。

程序代码:
#include <stdio.h>

 
#define MAX_M    64
#define MAX_N    64

 
int MaxRect(char *map, int rows, int cols)

 {
     int max = 0, i, j, k, t;
     for(i = 0; i < rows; i++)
     for(j = 0; j < cols; j++)
     {
         if(map[i * cols + j]) continue;
         for(k = 1; i + k < rows && j + k < cols; k++)
         {
             for(t = 0; t <= k; t++) if(map[(i + k) * cols + j + t]) break;
             if(t <= k) break;
             for(t = 0; i < k; t++) if(map[(i + k + t) * cols + j]) break;
             if(t < k) break;
         }
         if(k > max) max = k;
     }
     return max;

 }

 
int main()

 {
     char map[MAX_M * MAX_N];
     int rows, cols, count, i;
     for(;;)
     {
         scanf("%d%d", &rows, &cols);
         if(rows == 0 || cols == 0) break;
         count = rows * cols;
         for(i = 0; i < count; scanf("%d", &map[i++]));
         printf("%d\n", MaxRect(map, rows, cols));
     }
     return 0;

 }

重剑无锋,大巧不工
2011-07-27 00:41
好孩子好宝贝
Rank: 1
等 级:新手上路
帖 子:35
专家分:2
注 册:2011-7-26
收藏
得分:0 
优化。。。


你的时间比我用的多。。。本来以为我想错啦,到网站上去OJ一下,答案是错误,他说时间超时。。。。。


上面那个网站就是那个题目的原题。。。。。。

这个题目是动态规划问题。。。。

这样虽然不是很好的DP解法。。但是真的想不到其他的,要是另一样的话那样就会发跟多的时间空间。。。。。。
2011-07-27 08:33
好孩子好宝贝
Rank: 1
等 级:新手上路
帖 子:35
专家分:2
注 册:2011-7-26
收藏
得分:0 
你用啦三成for一般的OJ上市通不过的。。。。。。。。
2011-07-27 08:38
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
回复 好孩子好宝贝
本来没当回事的一道题,你的质疑再次提起了我的兴趣。
我重新分析了题目,构造出了下面的算法。你可以认为它是动态规划法,其实严格说来,它是贪心算法,因为它有很强的最优子结构。
算法很简单,你一看就明白了。其时间复杂度是O(n)。
为了保证代码的正确性,我亲自去你给的OJ提交了一次(虽然我不喜欢这个OJ)。AC。耗时367ms。
很高兴和你讨论问题
程序代码:
#include <stdio.h>

 
#define MAX_M    3000
#define MAX_N    3000

short int MAP[MAX_M][MAX_N];

 
int MaxRect(short int map[][MAX_N], int rows, int cols)
{
    int max = 0, min, i, j;
    for(i = 0; i < rows; i++)
    for(j = 0; j < cols; j++)
    {
        if(map[i][j] < 0) continue;
        if(i == 0 || j == 0) min = 0;
        else
        {
            min = map[i - 1][j];
            if(map[i - 1][j - 1] < min) min = map[i - 1][j - 1];
            if(map[i][j - 1] < min) min = map[i][j - 1];
            if(min < 0) min = 0;
        }
        map[i][j] = min + 1;
        if(max < map[i][j]) max = map[i][j];
    }
    return max;
}

 
int main()

 {
     int rows, cols, i, j, t;
     for(;;)
     {
         scanf("%d%d", &rows, &cols);
         if(rows == 0 || cols == 0) break;
         for(i = 0; i < rows; i++)
         for(j = 0; j < cols; j++)
         {
             scanf("%d", &t);
             MAP[i][j] = (t) ? -1 : 0;
         }
         printf("%d\n", MaxRect(MAP, rows, cols));
     }
     return 0;

 }

重剑无锋,大巧不工
2011-07-29 08:57
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
laoyang103早!我正在优化代码,不小心发现你也提交了这一题,而且占用内存一样,时间虽然差了一毫秒。莫非你也在测试我的代码?
已经优化完成。内存消耗由5892KB降到44KB。执行时间由367MS降到338MS。
之子于归 是我。

重剑无锋,大巧不工
2011-07-29 09:41
laoyang103
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:内蒙古包头
等 级:贵宾
威 望:19
帖 子:3082
专家分:11056
注 册:2010-5-22
收藏
得分:0 
我在学习你的代码

                                         
===========深入<----------------->浅出============
2011-07-29 09:49
laoyang103
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:内蒙古包头
等 级:贵宾
威 望:19
帖 子:3082
专家分:11056
注 册:2010-5-22
收藏
得分:0 
程序代码:
#include <stdio.h>
#include <string.h>
int main()
{
    int w[3001]={0}; //保存规划到前面行规划的结果,即每一列到本行并且包括本行的最长连续0长度
    //如果本行的某一列为1 那么这个结果必为0  w[0] 保存最有子结构的结果
    int l=0,r=0,i=0,max=0,temp=0,j = 0;
    while(scanf("%d%d",&l,&r))
    {        
        if(0 == l && 0 == r)
            break;
        for(i = 1;i<=l;i++)
        {
            max = 0;
            for(j = 1;j<=r;j++)//计算到本行的每一列连续0的个数
            {
                scanf("%d",&temp);
                if(0 == temp)
                    w[j]++;
                else
                    w[j] = 0;
            }
            for(j = 1;j<=r;j++)//遍历本行结果 更新w[0]
            {
                if(w[j]>w[0])//寻找连续的并且连续0个数大于w[0]的连续列个数
                    max++;
                else
                    max = 0;
                if(max>w[0])//如果找到了比w[0]大的  那么更新w[0]
                {
                    w[0]++;
                    break;
                }
            }
        }
        printf("%d\n",w[0]);
        memset(w,0,sizeof(w));//清空结果
    }
    return 0;
}

                                         
===========深入<----------------->浅出============
2011-07-29 10:32
laoyang103
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:内蒙古包头
等 级:贵宾
威 望:19
帖 子:3082
专家分:11056
注 册:2010-5-22
收藏
得分:0 
上面代码不是我发明的  我也是根据高人的指点

其思路为:按行规划  用一个数组记录前面已经规划行

并且包含当前正在规划行的最长连续0的长度  (w[0]号元素用来保存子结构结果)

然后在当前规划行更新结果  更新条件有两个  一个是找到最长连续零(w[j])个数大于w[0] 的列

另一个必须找到大于w[0]个这样的列  而且他们必须连续  就可以构成一个边长为w[0]+1的正方形了

我当时做这个题的时候也是用的矩形的动态规划  但是想成左上角相邻的三个取最大了  看到你矩形规划的代码学习一下

[ 本帖最后由 laoyang103 于 2011-7-29 10:43 编辑 ]

                                         
===========深入<----------------->浅出============
2011-07-29 10:39
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
呵呵,和我优化后的差不多。算法的本质并没有改变。
程序代码:
#include <stdio.h>

 
#define MAX_N    3000

int main()

 {
     int rows, cols, i, j, t, max, min;
     int a[MAX_N], b[MAX_N], *pa, *pb, *pt;
     for(;;)
     {
         scanf("%d%d", &rows, &cols);
         if(rows == 0 || cols == 0) break;
         max = 0;
         for(j = 0; j < cols; j++)
         {
             scanf("%d", &t);
             a[j] = (t) ? -1 : (max = 1);
         }
         pa = a;
         pb = b;
         for(i = 1; i < rows; i++)
         {
              scanf("%d", &t);
             pb[0] = (t) ? -1 : 1;
                for(j = 1; j < cols; j++)
             {
                 scanf("%d", &t);
                 if(t) pb[j] = -1;
                 else
                 {
                     min = pb[j - 1];
                     if(pa[j - 1] < min) min = pa[j - 1];
                     if(pa[j] < min) min = pa[j];
                     if(min < 0) min = 0;
                     pb[j] = min + 1;
                     if(pb[j] > max) max = pb[j];
                 }
            }
            pt = pa;
            pa = pb;
            pb = pt;
        }
        printf("%d\n", max);
     }
     return 0;

 }

重剑无锋,大巧不工
2011-07-29 10:50
世界模型
Rank: 4
等 级:业余侠客
威 望:1
帖 子:240
专家分:226
注 册:2010-9-12
收藏
得分:0 
mark
2011-07-29 11:10
快速回复:再出一题(祭祀广场)
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.034394 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved