【集训】DP & 搜索 & 线段树

集训Contest地址(VJ-Private): Contest 128411

Problem A (POJ 1018)

刚开始非常缺乏思路，后来听大家的讨论再研究一下发现这道题可以暴力枚举A的。 需要注意的是%f和%lf的问题。其实这个锅不能给C++/G++编译器，怪就怪当年的C标准委员会。double本来就应该是%lf的嘛！(至少scanf里面double必须是%lf的)

AC代码 View Source On GitHub

Problem B 

最大子矩阵。模板题。直接上成套模板（ACM模板——DP求解最长子段 最大子矩阵）

AC代码 View Source On GitHub

Problem C (POJ 1128)

十分闹心的一道题...折腾了三个多小时。最开始肯定是需要进行处理的，题目保证肯定能算出来四个角的位置（其实两个角就行了）于是就读图，算四个角，然后看四个角连成的边框上有哪些点，标记并存储这些点因为这些点就是覆盖在这个边框上的边框上的点（好绕...）然后才是比较闹心的地方，经过处理我们把这个点阵图转化为了一个有向图，然后要求的是一条经过所有点的路径（后来才知道这是拓扑！芜湖！）百度学习了好多拓扑算法，第一次WA。经Discuss提醒输出了所有的拓扑序列，AC。

AC代码 View Source On GitHub

Problem D (HDU 1698)

线段树题目，巨巨曾经讲过。今天自己写了一套比较好用的模板，这道题可以套用属性线段树的模板（ACM模板——各种各样的线段树）

AC代码 View Source On GitHub