今天看啥
热点:

sgu-250 Constructive Plan


题目大意:

给你一个N?M{0,1}矩阵,然后只有为0的地方可以可用,然后要你找出一个最大的C,输出所占大小,并且在原图中把所占的地方改成8,然后输出新的图。
PS:C的定义就是从上到下三个大小相邻且不为0的矩形,左边界需要对齐,并且上面和下面的矩形的右边界都要大于中间的矩形的右边界。

解题思路:

这道题我只想出了O(N3logN)的做法,虽然可以过,但是我写到一半写错了,然后偶然间看到了翱犇的代码,数了一下发现只有3个循环,”卧槽,N3,我于是赶快去膜拜了一下”。
O(N3logN)的算法在这里我就不再赘述了,网上估计可以找得到,我还是讲一下O(N3)的算法吧。

First:
我们用F[i][l][r]表示以第i行,第l列和第l+r?1列,为下边界的矩形最大的面积。如图:
这里写图片描述

Second:
然后我们令G[i][l][r]表示中间矩形以第i行,第l列和第l+r?1列,为下边界时前两个矩形的最大面积和。如图:
这里写图片描述
那么显然G[i][l][r]转移方程为(当第i行第l列到第l+r?1列都为0则为下式,否则为0)
G[i][l][r]=max(G[i?1][l][r]+r,r+max(F[i?1][l][k],k>r))
显然max(F[i?1][l][k],k>r)可以再循环中用一个变量记录更新以达到O(1)
Thrid:
H[i][l][r]表示最下面的矩形以第i行,第l列和第l+r?1列,为下边界时的最大答案。如图:
这里写图片描述
那么同G的计算类似,H[i][l][r]转移方程为(当第i行第l列到第l+r?1列都为0则为下式,否则为0)
H[i][l][r]=max(H[i?1][l][r]+r,r+max(G[i?1][l][k],k
然后这道题目就解决了。
输出就简单了

AC代码:

说明:本人由于太弱,边看翱犇的代码边学的题解,然后一不小心就写得和翱犇差不多了QAQ

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

int n,m;
int ch[200][200]={{0}};
short top[200][200][200]={{{0}}};
short F[200][200][200]={{{0}}};
short G[200][200][200]={{{0}}};
short H[200][200][200]={{{0}}};
int area=0;
int ai=0,al=0,ar=0;

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&ch[i][j]);
            top[i][j][1]=(short)(ch[i][j]^1)*(top[i-1][j][1]+1);
        }
    for(int i=n;i>=1;i--)
        for(int j=m;j>=1;j--)
        {
            if(ch[i][j]==1) continue;
            for(int k=2;k+j-1<=m && ch[i][k+j-1]==0;k++)
            {
                top[i][j][k]=min(top[i][j][1],top[i][j+1][k-1]);
                F[i][j][k]=top[i][j][k]*k;
            }
        }

    for(int i=2;i<=n;i++)
        for(int j=m;j>=1;j--)
        {
            if(ch[i][j]==1) continue;
            int k;
            for(k=1;k+j-1<=m && ch[i][k+j-1]==0;k++);k--;
            int Max=0;
            for(int r=m-j+1;r>k;r--)
                Max=max((int)F[i-1][j][r],Max);
            for(int r=k;r>=1;r--)
            {
                if(G[i-1][j][r]>0) G[i][j][r]=G[i-1][j][r]+r;
                if(Max>0) G[i][j][r]=max((short)(Max+r),G[i][j][r]);
                Max=max((int)F[i-1][j][r],Max);
            }
        }
    for(int i=2;i<=n;i++)
        for(int j=m;j>=1;j--)
        {
            if(ch[i][j]==1) continue;
            int Max=0;
            for(int k=1;k+j-1<=m && ch[i][k+j-1]==0;k++)
            {
                H[i][j][k]=max((H[i-1][j][k]>0)*(H[i-1][j][k]+k),(Max>0)*(Max+k));
                Max=max((int)G[i-1][j][k],Max);
                if(H[i][j][k]>area)
                {
                    area=H[i][j][k];
                    ai=i,al=j,ar=k;
                }
            }
        }
    if(area<5) cout<<-1<0;ai--)
            for(int i=1;i<=ar;i++)
                ch[ai][al+i-1]=8;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
                printf("%d ",ch[i][j]);
            puts("");
        }
    }
    return 0;
}

www.bkjia.comtruehttp://www.bkjia.com/cjjc/1004144.htmlTechArticlesgu-250 Constructive Plan 题目大意: 给你一个 N?M 的 {0,1} 矩阵,然后只有为 0 的地方可以可用,然后要你找出一个最大的 C ,输出所占大小,并...

相关文章

相关搜索: sgu-250 Constructive Plan

帮客评论

视觉看点