P2733 家的范围 Home on the Range

心已赠人 2022-06-06 11:28 74阅读 0赞

[https://www.luogu.org/problemnew/show/2733][https_www.luogu.org_problemnew_show_2733]

*d**p*\[*i*\]\[*j*\]=*m**i**n*(*d**p*\[*i*−1\]\[*j*\],*d**p*\[*i*\]\[*j*−1\],*d**p*\[*i*−1\]\[*j*−1\])\+1(*a*\[*i*\]\[*j*\]=1)

其中 `dp[i][j]` 表示从左上角到(i,j)的最大正方形长度。

这题小正方形还会在大正方形里，所以还要再加上它们。

下面的程序读入好像有点问题..

#include<iostream>
    #include<cstdio>
    #include<cstring>
    
    using namespace std;
    const int maxn = 251;
    int n,a[maxn][maxn],dp[maxn][maxn],count[maxn];
    int main(){
        scanf("%d",&n);getchar();
        for(int i =1;i<=n;i++){
            for (int j =1,c;j<=n;j++){
                c = getchar();
                if (c=='1'){
                    a[i][j] = 1;
                }else if (c=='0'){
                    a[i][j] = 0;
                }
            }
            getchar();
        }
        memset(count,0,sizeof(count));
        //if (a[1][1]==true) dp[1][1] = 1;else dp[1][1] = 0;
        for (int i =1;i<=n;i++)
            for(int j =1;j<=n;j++){
                if (a[i][j]){
                    dp[i][j] = min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1;
                    count[dp[i][j]]++;
                }
            }
        for (int i = n;i>=2;i--){
            count[i-1] += count[i];//从后往前遍历，不用考虑一个正方形可以放几个小正方形
        }
        for (int i = 2;i<=n;i++){
            if (count[i]!=0) cout<<i<<" "<<count[i]<<endl;
        }
    }

[https_www.luogu.org_problemnew_show_2733]: https://www.luogu.org/problemnew/show/2733

发表评论取消回复

表情：

评论列表（有 0 条评论，74人围观）

还没有评论，来说两句吧...

相关阅读

相关 JavaRestClient操作Elasticsearch范围查询(range)

导包导包可以根据 [文档][Link 1] 里导入依赖这里就不写依赖了范围查询(range) import com.google.gson.Gs

Love The Way You Lie/ 2022年12月23日 15:27/ 0 赞/ 244 阅读

相关 Til the Cows Come Home

Til the Cows Come Home <table> <tbody> <tr> <td><strong>Time Limit:</strong>&n

小灰灰/ 2022年06月11日 07:55/ 0 赞/ 121 阅读

相关 P2733 家的范围 Home on the Range

[https://www.luogu.org/problemnew/show/2733][https_www.luogu.org_problemnew_show_2733]

心已赠人/ 2022年06月06日 11:28/ 0 赞/ 75 阅读

相关 leetcode 715. Range Module 范围模型

A Range Module is a module that tracks ranges of numbers. Your task is to design and imp

电玩女神/ 2022年06月03日 09:40/ 0 赞/ 143 阅读

相关 Excel Range获取多个范围

workSheet.get_Range("T4:U19,A4:A19"); 获取范围的时候，其实可以获取多个范围。这句话的意思等同于 workSh

约定不等于承诺〃/ 2022年05月24日 02:38/ 0 赞/ 165 阅读

相关 SAP Number range 编号范围用法

1.通用Tcode:SNRO 常用维护特定Number range Tcode: <table style="width:300pt"> <tbody>

短命女/ 2022年04月03日 06:16/ 0 赞/ 614 阅读

相关 Neither the JAVA_HOME nor the JRE_HOME environment variable is defined

【背景】从idea要启动Tomcat时，结果发现报错了，还带乱码的。。。 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpd

妖狐艹你老母/ 2022年03月15日 06:10/ 0 赞/ 166 阅读

相关 Neither the JAVA_HOME nor the JRE_HOME environment variable is defined

Centos7.5 启动tomcat报错报错: Neither the JAVA_HOME nor the JRE_HOME environment varia

亦凉/ 2022年01月06日 00:55/ 0 赞/ 213 阅读

相关列表 -- list、元组 -- tuple、range -- 范围

列表 -- list 有序,可变的,索引, 作用:存储数据的,支持很多种数据类型定义方式: lst = [1,"alex","黑哥"] 增:

红太狼/ 2021年11月16日 11:10/ 0 赞/ 330 阅读

相关 C. Going Home （抽屉原理、范围、暴力）

[题目][Link 1] [抽屉原理][Link 2] 看题目的数据，其中可以发现两个数相加结果最大也只是5e6，根据抽屉原理，只要有5e6+1个数就至少会有两个数

Bertha 。/ 2021年09月07日 06:18/ 0 赞/ 276 阅读