百练OpenJudge上2791题矩阵覆盖用动态规划的解法在平面上给出了n个点,现在需要用一些平行于坐标轴的矩形把这些点覆盖住.每个点都需要被覆盖,而且可以被覆盖多次.每个矩形都至少要覆盖两

题目详情

百练OpenJudge上2791题矩阵覆盖用动态规划的解法
在平面上给出了n个点,现在需要用一些平行于坐标轴的矩形把这些点覆盖住.每个点都需要被覆盖,而且可以被覆盖多次.每个矩形都至少要覆盖两个点,而且处于矩形边界上的点也算作被矩形覆盖.注意：矩形的长宽都必须是正整数,也就是说矩形不能退化为线段或者点.
现在的问题是：怎样选择矩形,才能够使矩形的总面积最小.
怎么用动态规划做?

▼优质解答

答案和解析

可以转换成最小子序列（也就是降一维）
双重for循环枚举长的边界另外一重用最小子序列一维动态规划
你先自己百度一下吧.不会再说

看了百练OpenJudge上279...的网友还看了以下：

两对等位基因控制一个性状的“特殊遗传分离比”求速解,详解,我没明白为什么两对等位基因控制的性状（F 　2020-05-17 …

某甲于上午9时15分钟由码头划船出游,计算最迟于12时返回原码头...某甲于上午9时15分钟由码头　2020-05-20 …

问题问一道地理题目9,关于降水的时空分布的,正确的是（）A,沿海地区降水一定丰富B,地形雨都出现在　2020-05-23 …

关于1.4.9的多种规律从1.4.9中可以看出的规律是：1.4.9.16.25.36……,又可以看　2020-07-18 …

1.’第一题：一个班级有17个女生,其中5人每天都是步行到校,7人有自行车可用,9人可乘汽车,但5+ 　2020-11-03 …

用6、3、8、9和5个0按要求写出9位数.（1）最大的数用6、3、8、9和5个0按要求写出9位数.（　2020-11-18 …

求一英文委托书,要正规写法哟,大概内容为：委托书委托人：顾湘君,女,于1925年2月26日出生王耀章　2020-11-22 …

英语翻译他们打算建一座新大楼,它将于明年9月钱完工前天晚上太冷了.,以至于谁都没有出门这本书太好看了　2020-11-27 …

一共有100个包子,共10笼其中有一笼里面每个包子的重量都是9两,而其...一共有100个包子,共1 　2020-11-30 …

图为南极洲及我国三个南极科考站的位置图，结合所学知识回答8〜9题．当我省各地日出时刻（地方时）处于一　2020-12-22 …