8月做题小结(贪心)

 

因为做手术,耽误了不少时间。

 

贪心的就是选择当前最优(大,小)的,所以经常要用排序,最大堆,枚举。

 

排序

2782 Bin Packing 选定一个,再选一个尽可能大的

 

枚举

3066 Maximum 这题过的糊里糊涂的,不知道是不是数据弱的缘故,每次在条件允许的范围下选择尽可能大的数

 

2076 All Roads Lead to Albuquerque, er, Rome 一开始直接想的是O(n^3)的算法,想不出来。一看题解居然是从O(n^4)优化到O(n^3),以后直接想想不出来的话,可以先想复杂度高的,再优化。和1153类似,枚举过渡法。

 

 

动态规划

1784 Huffman's Greed 比较经典的动态规划,除了题名,跟贪心没什么关系

 

最大堆

2786 Keep the Customer Satisfied 题目给了Hint也就简单多了,第一次写最大堆类,每次能添加的时候添加,不能添加的时候再看能不能换。

 

3110 Jenny's First Exam 复用了最大堆类,不用重新写,还写了个日期类。从大到小开始枚举,用最大堆维护起始日期。

 

 

原文地址:https://www.cnblogs.com/xchaos/p/2688501.html