【2019暑假】6-28

By shy

——回归NOIP

提高新生涯的第一天


1. 【NOIP2011 day1 T1】铺地毯

题意:用n个矩形覆盖平面直角坐标系,后放的矩形覆盖前面放好的矩形上,给出每个矩形的左下角的坐标(a,b)以及矩形在 x轴和 y 轴方向的长度,求覆盖地面某点(x,y)的最上面的那个矩形的编号。

Solution

水题。很早就做过

由题意可知对于一个点来说后放的矩形一定在先放的上面,所以该题是求覆盖在店上(x,y)的最后一个矩形。

于是先将所有矩形输入,按照输入顺序反向枚举每一个矩形,如果发现一个矩形包括了这个点,直接将编号输出并退出循环。

继续阅读【2019暑假】6-28

DP

https://www.zhihu.com/question/23995189/answer/613096905

【DP三连】

设计DP算法,往往可以遵循DP三连:

我是谁? ——设计状态,表示局面
我从哪里来?
我要到哪里去? ——设计转移

设计状态是DP的基础。接下来的设计转移,有两种方式:一种是考虑我从哪里来(本文之前提到的两个例子,都是在考虑“我从哪里来”);另一种是考虑我到哪里去,这常见于求出f(x)之后,更新能从x走到的一些解。这种DP也是不少的,我们以后会遇到。

作者:阮行止
链接:https://www.zhihu.com/question/23995189/answer/613096905
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。