20170701总结

今天是的最后一节课。上午讲了最后两种较难的，即状压和数位。状压我较为熟悉，思想和细节都不复杂。而数位虽然思想也较为简单，但从写码的细节上来说，较为复杂，会涉及到分类。周日写两道数位的题来看看。下午是优化。先复习了凸包算法（水平扫描），然后讲斜率优化。这种优化思想是把方程转化成或的形式，其中是常数，描出所有的，然后用凸包求上凸壳或下凸壳，使得dp过程中所用的总是可用的最优状态。接下来是矩阵快速幂优化，个人觉得就是把连加的方程转化成连乘的方程，转化为幂后就可用矩阵快速幂了。这两种方法都对数学有要求，虽然听起来不难，但自己推会有些困难，应多加练习。最后是杂题选讲，其实就是对前面两种优化的巩固，题目的方程转换模式都是差不多的。优化需要多写写题，希望以后在考试中能接触到。