首页 > 其他分享 >CF1775F Laboratory on Pluto - dp - 构造 -

CF1775F Laboratory on Pluto - dp - 构造 -

时间:2023-01-16 20:44:19浏览次数:54  
标签:CF1775F Pluto Laboratory 矩形 补成 dp

题目链接:https://codeforces.com/contest/1775/problem/F

题解:
首先考虑第一问
考虑将答案的图形补成一个矩形
显然出现凹槽不优,因此可以看成一个矩阵去掉几个角之后的图形
因此补成矩形之后周长仍然不变
注意到补成矩形之后的长和宽相差最多1的时候一定可以取到最优值(长和宽相差越小周长越小)
因此可以枚举,相差1且面积大于 \(n\) 的时候停止即可,注意输出的时候去掉的是个角!

再考虑第二问

标签:CF1775F,Pluto,Laboratory,矩形,补成,dp
From: https://www.cnblogs.com/SkyRainWind/p/17056271.html

相关文章

  • 内网Linux下安装Nginx1.23,添加stream模块实现tcp/udp代理转发
    环境:centos7.6ngx_stream_core_module这个模块在1.9.0版本后将被启用。但是并不会默认安装,需要在编译时通过指定--with-stream参数来激活这个模块,window下并不支持udp......
  • Vulnhub之Dobby详细解题过程(不同的获得wordpress后台密码方法)
    Dobby作者:jason_huawen靶机信息名称:Hogwarts:Dobby地址:识别目标主机IP地址─(kali㉿kali)-[~/Vulnhub/Dobby]└─$sudonetdiscover-ieth1-r192.168.56.0/2......
  • 区间DP-二维前缀和-差分-6292. 子矩阵元素加 1
    304.二维区域和检索-矩阵不可变DescriptionDifficulty:中等RelatedTopics:设计,数组,矩阵,前缀和给定一个二维矩阵matrix,以下类型的多个请求:计算其子矩形......
  • 用模仿学习来学习POMDP中的信念表示
    一、研究对象本文研究了POMDP的模仿学习问题,具体来说本文在POMDP中引入了一种的信念表示学习方法,用于生成对抗模仿学习,不同于以往单独训练信念模块和策略,我们对信念模块和......
  • 怎么取消 Windows Server 2012 RDP 限制每个用户只能进行一个会话
    在WindowsServer2008/2008R2上,如果希望多个远程用户使用同一个账号同时访问服务器的RemoteDesktop(RDP),只需通过管理工具-远程桌面下的“远程桌面会话主机配置”进行......
  • Sub-process /usr/bin/dpkg returned an error code (1)解决方案
    第一步:创建一个干净的dpkg文件夹sudomv/var/lib/dpkg/info/var/lib/dpkg/info.bak//先将info文件夹更名sudomkdir/var/lib/dpkg/info//再新建一个新的info文件夹......
  • 区间dp模板
    该死的csdn登陆不上去了,为了防止区间dp模板丢失,在这里再存一份然后是左右取数字的问题,我记得20年的时候我应该看过这题,是有一个数列,前后取若干个数字,问先手能取最大值那......
  • bzoj 2554 Color 期望DP
    期望DP枚举最终能成为哪个颜色,把这个颜色看做白球,其余颜色看成黑球。最后分别把每种颜色的期望加起来就行。考虑当前有i个白球,全变成白球期望步数设为f[i]一次操作可能......
  • 计数 dp 目录
    数え上げテクニック集笔记。引言OI中有三大专题:dp,数据结构,图论。而在这三大专题中,因为dp是从小问题的解法上升至大问题的解法的关键;所以dp,在这三大专题中,优先性是......
  • 动态dp
    两天时间学习了动态dp。题目洛谷P4719首先我们假设如果它是普通dp。设计状态\(f[i][0/1]\)表示以\(i\)为根的子树中选或不选\(i\)结点的最大独立集的值。状态转移\(f[......