首页 > 其他分享 >E - Defect-free Squares

E - Defect-free Squares

时间:2023-07-25 22:26:37浏览次数:42  
标签:Squares 题意 int d% Defect free 3001 include dp

Linkkkkkkkkkkkk

这其实是个dp问题

可以拆成一个个dp小问题,然后求和,这个小问题就是以\((i,j)\)为右下角方块下会有多少矩形,然后把每一个位置加起来就行了。

应注意到以下命题充要性成立:如果\((i,j)\)位置存在一个正方形长度为n满足题意,那么在\((i-1,j),(i,j-1),(i-1,j-1)\)处都应存在着长度为 n-1的矩形满足题意

这样就可以进行dp了

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<ctime>
#include<bitset>
using namespace std;
int ma[3001][3001];
int h,n,m;
int dp[3001][3001];
int x,y;
long long ans;
int main(){
	scanf("%d%d%d",&n,&m,&h);
	for(int i=1;i<=h;++i){
		scanf("%d%d",&x,&y);
		ma[x][y]=1;
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(ma[i][j]) dp[i][j]=0;
			else dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
			ans+=dp[i][j];
		}
	}
	cout<<ans;
	return 0;
}

标签:Squares,题意,int,d%,Defect,free,3001,include,dp
From: https://www.cnblogs.com/For-Miku/p/17581187.html

相关文章

  • Fastbin Double Free
    参考:shellphish/how2heap:Arepositoryforlearningvariousheapexploitationtechniques.(github.com)Glibc-2.23实验代码#include<stdio.h>#include<stdlib.h>intmain(){ int*a=malloc(8); int*b=malloc(8); int*c=malloc(8); free......
  • E - Defect-free Squares
    E-Defect-freeSquares(atcoder.jp)题意:一个H*W的矩形上有几个块有洞,问你没有洞的正方形有多少个两种做法,DP和二分前缀和DP是官方题解先是二分前缀和做法,当时没想到前缀和可还行。。先弄好前缀和,然后我们考虑用(i,j)作为正方形左上角能贡献多少个正方形,显然(i,j)作为左上......
  • Defect-freeSquares
    [ABC311E]Defect-freeSquares考虑令\(f[i][j]\)表示以\((i,j)\)为右下角的最大正方形的边长,以其为右下角的正方形恰好为\(f[i][j]\),答案就是\(\sumf[i][j]\)。然后考虑转移。对于一个格子,如果要扩充正方形,必定要往左上角、左、上三个方向扩张,且取决于最小者,即\(f[i][j......
  • 使用Free Pascal开发STM32程序
    使用FreePascal开发STM32程序前言大部分人都知道嵌入式开发,一般用的都是C语言,但是实际上,除C语言之外还有许多语言都可以开发,本文将介绍使用FreePascal(简称FPC)开发STM32程序的方法。你可以进FreePascal的官网看看,其第一段话就是说这个编译器支持多少处理器多少操作系统的,事实......
  • FreeSWITCH添加g729编码及pcap音频提取
    操作系统:debian11(bullseye,docker)、Windows10_x64FreeSWITCH版本:1.10.9Docker版本:23.0.6Python版本 : 3.9.2 日常工作中,有时候会遇到g729编码的相关内容,但FreeSWITCH默认是不支持g729编码转码的,今天记录下使用开源的bcg729进行g729转码的过程(本文仅作技术研究,......
  • python sip freeswitch
    PythonSIPandFreeSWITCHIntroductionInthisarticle,wewillexplorehowtousePythontointeractwithFreeSWITCH,anopen-sourcetelephonyplatform.WewillspecificallyfocusonutilizingtheSessionInitiationProtocol(SIP)moduleinPythontoest......
  • new/delete/malloc/free
    new/deletenew和delete是C++中的运算符,不是库函数,不需要库的支持。new的工作机理string*sp=newstring("avalue");//一个new表达式new表达式调用一个operatornew(或者operatornew[])的标准库函数,该函数分配一个原始的,足够大小的,未命名的内存空间编译器运行相应的构造函数......
  • 论文翻译: FREEVC:朝着高质量、无文本、单次转换声音的目标迈进
    原文:FREEVC:TOWARDSHIGH-QUALITYTEXT-FREEONE-SHOTVOICECONVERSION原文地址:https://ieeexplore.ieee.org/abstract/document/10095191 个人总结:1.提出mel谱缩放增强方法。2.基于VITS框架进行改进,BUT在对照实验中缺没有对比VITS3.引入WavLM模型提高VC模型对说话人内容......
  • Freertos学习09-软件定时器
    一、概述软件定时器是一种在单片机上实现定时功能的方法,可以用于周期性地执行任务或者延时执行任务。软件定时器由FreeRTOS内核实现,不需要硬件支持。软件定时器只有在软件定时器回调函数被调用时才需要占用CPU时间。本节主要设计以下内容:软件定时器的API介绍实例测试......
  • FreeType 控制台渲染字形轮廓笔记
    项目里用到了FreeType解析字体,这里只为了更方便入手FreeType,简单读取字体文件,并在控制台绘制制定字符轮廓,以字符A为例:初始化FreeType,加载字体文件#include<freetype2/ft2build.h>#includeFT_FREETYPE_H#include<iostream>#include<math.h>usingnamespacestd;......