在上周的CCPC秦皇岛中，我们在热身赛就“出师不利”，被一道计算几何斩下马。所以我开始祈祷天堂没有计算几何（误），所以我开始主攻计算几何这一部分。在这篇BLOG中，我们就来一同解决长方体两点的最短表面距离这一看似简单实则十分繁杂的问题吧！由于这个问题在网络上的讨论甚少，仅有的一份CSDN上的模板也是错误的，所以本片BLOG也是没有任何参考的完全原创BLOG。如果本篇BLOG出现任何错误，欢...
好久没有更新计算几何的相关博客了。最近见到几道矩阵最大子矩形问题的题目，感觉可以拓展到计算几何上解决最大子矩形问题。下面就让我们逐一看看这些个问题吧。 矩阵最大子矩形问题 问题描述 在矩阵最大子矩形问题相关问题中，最出名的要数最大全零子矩形了。下面就让我们来看看问题描述。 题目大意：在一个给定的大小为a*b矩形网格中有n个障碍点，要找出网格内部不包含任何障碍点，且边界与坐标轴平行的最大子...
说到动态规划，就不得不提到区间动态规划这一重要分支。到现在都还记得当年还是OIER的时候第一次了解到区间动态规划时被其精妙的设计所折服的喜悦。所以现在就让我们一同学习以下区间动态规划，回顾当年的那份喜悦吧！ 区间动态规划 在之前的BLOG中，我们已经学习了动态规划的一些基本知识。那么什么是区间动态规划？和我们之前学过的线性动态规划有什么区别呢？ 区间动态规划，从名字来看就是在一段区间上进...
说到动态规划，就不得不提经典的背包问题了。在这篇BLOG中，我们将一同学习几种经典的背包模型，让你成为背包小能手。 背包问题 在学习各种背包问题之前，我们应该先了解一下什么是背包问题。 所谓背包问题，指的是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放...
我们终于来到了动态规划专题啦。在接下来的几篇BLOG中，我将会由浅入深，逐一讲解现在常见的几种动态规划类型。由于动态规划更多的是推导的过程而不是代码部分讲解，所以在接下来的几部分我也会拿出更多的经典模型结合讲解，培养同学们推方程的能力。下面就让我们进入动态规划专题的第一篇，线性动态规划入门吧！ 动态规划历史 动态规划，这个看起来非常年轻的算法，其实早在1957念就被贝尔曼在《动态规划》一...