题解

51 条题解

  • 0
    @ 2016-11-17 16:12:28
    #include <iostream>
    #include <string.h>
    using namespace std;
    
    const int maxn =2001;
    int map[maxn][maxn]={0};
    int n,m;
    int dp[maxn][maxn]={0};
    int max_squre(int target,int &ans){
        memset(dp,0,sizeof(dp));
        for(int i =1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(map[i][j]==target){
                    dp[i][j] = min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1;
                    ans = max(dp[i][j]*dp[i][j],ans);
                }
            }
        }
    }
    
    
    int max_rectangle(int target,int& ans){
        int dpl[2][maxn],dpr[2][maxn],templ[maxn],tempr[maxn];
        memset(dp,0,sizeof(dp));
        memset(dpl,0,sizeof(dpl));
        memset(dpr,0,sizeof(dpr));
        memset(templ,0,sizeof(templ));
        memset(tempr,0,sizeof(tempr));
        
        
        
        int mx =0;
        for(int i =1;i<=m;i++){
            dpl[0][i]=0,dpr[0][i]=m;
        }
        for(int i =1;i<=n;i++){
            int tmp =1;
            for(int j =1;j<=m;j++){
                if(map[i][j]!=target) tmp = j+1;
                else templ[j] = tmp;
            }
            tmp =m;
            for(int j=m;j>=1;j--){
                if(map[i][j]!=target) tmp = j-1;
                else tempr[j] = tmp;
            }
            for(int j =1;j<=m;j++){
                if(map[i][j]!=target){
                    dp[i&1][j]=0,dpl[i&1][j] =1,dpr[i&1][j] = m;
                    continue;
                }
                dp[i&1][j] = dp[(i&1)^1][j]+1;
                dpl[i&1][j] = max(dpl[(i&1)^1][j],templ[j]);
                dpr[i&1][j] = min(dpr[(i&1)^1][j],tempr[j]);
                mx = max((dpr[i&1][j]-dpl[i&1][j]+1/*加上自己*/)*dp[i&1][j],mx);
                
            } 
            
        }
        ans = max(ans,mx);
        
    }
    int main(){
        cin>>n>>m;
        
        //pre init
        for(int i =1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>map[i][j];
                if((i+j)%2==1){
                    map[i][j] = 1-map[i][j];
                }
            }
        }
        
        
        //最大正方形 
        int ans=0;
        
        max_squre(1,ans);
        max_squre(0,ans);
        
        cout<<ans<<endl;
        
        ///最大子矩阵 
        max_rectangle(1,ans);
        max_rectangle(0,ans);
        cout<<ans<<endl;
        
        return 0;
    }
    

    测试数据 #0: Accepted, time = 15 ms, mem = 31952 KiB, score = 10
    测试数据 #1: Accepted, time = 31 ms, mem = 31948 KiB, score = 10
    测试数据 #2: Accepted, time = 31 ms, mem = 31948 KiB, score = 10
    测试数据 #3: Accepted, time = 140 ms, mem = 31956 KiB, score = 10
    测试数据 #4: Accepted, time = 125 ms, mem = 31952 KiB, score = 10
    测试数据 #5: Accepted, time = 843 ms, mem = 31952 KiB, score = 10
    测试数据 #6: Accepted, time = 1921 ms, mem = 31948 KiB, score = 10
    测试数据 #7: Accepted, time = 1484 ms, mem = 31944 KiB, score = 10
    测试数据 #8: Accepted, time = 3046 ms, mem = 31952 KiB, score = 10
    测试数据 #9: Accepted, time = 3125 ms, mem = 31952 KiB, score = 10
    Accepted, time = 10761 ms, mem = 31956 KiB, score = 100

    • @ 2016-11-17 16:18:58

      加上sync_with_stdio(false);
      可以做到
      测试数据 #0: Accepted, time = 15 ms, mem = 31940 KiB, score = 10
      测试数据 #1: Accepted, time = 15 ms, mem = 31936 KiB, score = 10
      测试数据 #2: Accepted, time = 31 ms, mem = 31936 KiB, score = 10
      测试数据 #3: Accepted, time = 93 ms, mem = 31940 KiB, score = 10
      测试数据 #4: Accepted, time = 93 ms, mem = 31940 KiB, score = 10
      测试数据 #5: Accepted, time = 578 ms, mem = 31940 KiB, score = 10
      测试数据 #6: Accepted, time = 1359 ms, mem = 31940 KiB, score = 10
      测试数据 #7: Accepted, time = 1015 ms, mem = 31936 KiB, score = 10
      测试数据 #8: Accepted, time = 2062 ms, mem = 31936 KiB, score = 10
      测试数据 #9: Accepted, time = 2109 ms, mem = 31936 KiB, score = 10

  • 0
    @ 2016-07-20 22:35:07

    {
    测试数据 #0: Accepted, time = 0 ms, mem = 824 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 820 KiB, score = 10
    测试数据 #2: Accepted, time = 15 ms, mem = 820 KiB, score = 10
    测试数据 #3: Accepted, time = 78 ms, mem = 820 KiB, score = 10
    测试数据 #4: Accepted, time = 46 ms, mem = 824 KiB, score = 10
    测试数据 #5: Accepted, time = 734 ms, mem = 820 KiB, score = 10
    测试数据 #6: Accepted, time = 2531 ms, mem = 820 KiB, score = 10
    测试数据 #7: Accepted, time = 1281 ms, mem = 824 KiB, score = 10
    测试数据 #8: Accepted, time = 5031 ms, mem = 820 KiB, score = 10
    测试数据 #9: Accepted, time = 7046 ms, mem = 824 KiB, score = 10

    用h[x]表示处理到当前行时第x列的连续01串长度,v[k]表示当前行起始于k的所有纵向连续01串的高度最小值(前提是从x开始横向的串是连续的),也就是矩阵的高。
    p的含义需要解释一下。p是在当前行,处理到某个位置时,连续01串的起始位置,在p到当前位置的横向串都是连续的。p保证了上面提到的v[k]到横向的连续(for k:=p to j,k一定在p之后)。横纵都连续,那这一定是个完整的矩阵,长乘高得面积。
    边界处理很特殊,所以第一行的读入、每一行第一个的读入、处理都单独拿出来了,以及最后一个也要专门处理一下。
    这个算法有个重要的优化。不优化的话会超时0.015s......标出来了。
    var
    n,m,i,j,k,p,l,ans:longint;
    map:array[1..2000,false..true]of shortint;
    h,v:array[1..2000]of longint;
    function min(a,b:longint):longint;
    begin
    IF A<B THEN EXIT(A) ELSE EXIT(B);
    END;
    function max(a,b:longint):longint;
    begin
    IF A>B THEN EXIT(A) ELSE EXIT(B);
    END;
    begin
    readln(n,m);
    ans:=0;
    l:=1;
    //初始化第一行
    for i:=1 to m do
    begin
    read(map[i,true]);
    h[i]:=1;
    if (map[i,true]=map[i-1,true]) then//横向01串是否连续
    p:=i;//不连续,将连续横向01串的起始位置设为j(实际保存为j-1)
    for k:=p to i do//连续,更新矩阵高度,求最大面积
    ans:=max(ans,(i-k+1));

    end;

    for i:=2 to n do
    begin
    p:=0;
    read(map[1,(i and 1)=1]);
    if (map[1,(i and 1)=1]=map[1,(i and 1)=0]) then
    h[1]:=1//不连续,将高度设为1
    else
    inc(h[1]);//连续,高度加1
    v[1]:=h[1];
    ans:=max(ans,v[1]);
    for j:=2 to m do
    begin
    read(map[j,(i and 1)=1]);
    //第j列当前连续01串长度,
    if (map[j,(i and 1)=1]=map[j,(i and 1)=0]) then
    h[j]:=1//不连续,将高度设为1
    else
    inc(h[j]);//连续,高度加1
    v[j]:=h[j];//v[x]记录下了横向起始于x位置,到当前处理位置中,所有纵向01串的最小高度(木桶原理),即01矩阵高度
    if (map[j,(i and 1)=1]=map[j-1,(i and 1)=1]) then//横向01串是否连续
    begin
    //不连续,先赶紧更新之前的数据(因为之前有延迟,v[k]值不变就不计算),将连续横向01串的起始位置设为j
    for k:=p to j-1 do//对于j=m时的特殊对待
    begin
    ans:=max(ans,v[k]*(j-k));
    l:=max(l,min(v[k],j-k));
    end;
    p:=j;
    end;
    for k:=p to j-1 do//连续,更新矩阵高度,求最大面积
    if h[j]<v[k] then
    //(优化:延迟计算)只有在发生v[k]变动的时候才计算和更新,因为在v[k]值不变的情况下,v[k]*(j-k)一定是随j递增的。此时计算的矩阵长度是k到j回退到前一个v[k]没有变动的的位置。但这样的延迟计算会导致当j等于m且串依然连续时,不会计算更新。所以对于j=m要特殊计算。
    begin
    ans:=max(ans,v[k]*(j-k));
    l:=max(l,min(v[k],j-k));
    v[k]:=h[j];
    end;
    end;
    for k:=p to m do//对于j=m时的特殊对待
    begin
    ans:=max(ans,v[k]*(m-k+1));
    l:=max(l,min(v[k],m-k+1));
    end;
    readln;
    end;
    writeln(l*l);
    write(ans);
    end.

  • 0
    @ 2013-11-03 19:25:30

    按照1255,极大化思想写就行了,但是还有一些不同点。
    1255是如果是0就不能放,但是这里就是我和上面那行不同,我也可以单独成行,相当于也可以放。
    这点需要注意。另外细心即可。
    dxe

  • 0
    @ 2010-07-14 09:53:12

    直接悬线,第一二问全部解决

    第一问都用盖房子方法...我感觉很诧异

  • 0
    @ 2009-11-11 17:14:05

    无情的秒杀……

    程序有点错误,谁帮我看看

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案错误...

     ├ Hint: 恩,900*1200 ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 07:答案正确... 72ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 25ms

    ├ 测试数据 10:答案正确... 56ms

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:90 有效耗时:153ms

    var

    n,m,i,j,ans,k,L,y,x,ans2:longint;

    a:array[0..1,1..2000] of byte;

    f:array[0..1,0..2000] of longint;

    g,h:array[0..1,0..2000,1..2] of longint;

    function min(x,y,z:longint):longint;

    begin

    min:=x;

    if y

  • 0
    @ 2009-11-10 08:54:04

    编译通过...

    ├ 测试数据 01:答案正确... 134ms

    ├ 测试数据 02:答案正确... 244ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 338ms

    ├ 测试数据 07:答案正确... 322ms

    ├ 测试数据 08:答案正确... 56ms

    ├ 测试数据 09:答案正确... 338ms

    ├ 测试数据 10:答案正确... 259ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:1691ms

    好丑……分数70-30-0-……-0-100……

    最近老是写很SB的错误

  • 0
    @ 2009-11-07 14:54:16

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 9ms

    ├ 测试数据 07:答案正确... 212ms

    ├ 测试数据 08:答案正确... 228ms

    ├ 测试数据 09:答案正确... 244ms

    ├ 测试数据 10:答案正确... 275ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:968ms

    第一次接触这种思想,受益匪浅

  • 0
    @ 2009-10-17 23:08:35

    WS....偷懒没有“滚”起来。。没有一次a可惜啊。。哎。今天初赛rp全散光了。orz。。

  • 0
    @ 2009-10-06 20:57:49

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 25ms

    ├ 测试数据 07:答案正确... 212ms

    ├ 测试数据 08:答案正确... 150ms

    ├ 测试数据 09:答案正确... 431ms

    ├ 测试数据 10:答案正确... 353ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:1171ms

    第363个AC!一次AC!

    Orz 王知昆大牛 的left,right,up方法!

    Orz!

  • 0
    @ 2009-09-24 19:04:55

    交了好多遍,终于过了,我居然没赋初值。

  • 0
    @ 2009-09-19 19:58:02

    Accepted 有效得分:100 有效耗时:12206ms

    有惊无险地过了 - -!

    我真是傻x,第一问算错了害我改了两天………………

    第二问不知道的自己想,不是特别难

  • 0
    @ 2009-09-16 20:18:37

    注意m和n 别搞混了

  • 0
    @ 2009-09-14 22:36:28

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 41ms

    ├ 测试数据 07:答案正确... 244ms

    ├ 测试数据 08:答案正确... 181ms

    ├ 测试数据 09:答案正确... 447ms

    ├ 测试数据 10:答案正确... 447ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:1360ms

    正方形=DP盖房子(我盖房子枚举+优化的说)

    矩形用模拟栈

    100题纪念

  • 0
    @ 2009-09-14 13:44:26

    最大子矩阵变形

  • 0
    @ 2009-09-03 09:44:12

    空间。。。

    WA了一次

    很WS的过了

  • 0
    @ 2009-08-31 02:31:15

    盖房子+最大子矩形(悬线法) DP

    O(NM)的时间

    内存受不了,只好“滚”了。

    真乃好题也~!!!

    n,m搞反了,超级郁闷……

  • 0
    @ 2009-08-26 18:53:42

    第一问: f=min(f,f);

    f=min(f,f);

    inc(f);

    发现错了吗? 我是一个下午之后才发现的

  • 0
    @ 2009-08-17 13:23:11

    j打成i折磨了我昨天一个下午,今天才发现.....

    感谢题解,WC2003王知昆的论文真让人受益匪浅啊~~

  • 0
    @ 2009-08-16 18:09:02

    ...好题阿~真是好题阿~~~~太经典了

    还是看RP的题阿。。。

  • 0
    @ 2009-08-07 22:48:39

    用A表示棋盘

    对于正方形,可以类似于盖房子的模型

    F=Min(F,F,F)+1

    条件为 (Not(A Xor A))And(A Xor A)And(A Xor A)

    即满足黑白相间的要求

    对于矩形,可以利用极大化思想

    F=H[J]*(R[J]-L[J]+1)

    其中H[J]表示A向上最多可以延伸的高度,L[J],R[J]表示向左、右可以延伸的宽度

    求L的代码如下

    L[1]:=1;

    For J:=2 to M do

    Begin

    L[J]:=J;

    While(L[J]>1)And(H[J]

信息

ID
1351
难度
7
分类
动态规划 | 单调性DP数据结构 | 点击显示
标签
(无)
递交数
1029
已通过
233
通过率
23%
被复制
3
上传者