昨天做了道贪心的题，最近都在做这个，今天先写下这题的报告。
题目：
http://acm.pku.edu.cn/JudgeOnline/problem?id=1230

其实如果掌握了动态规划的方法，那对于贪心就只要找到它的贪心性质就可以了，因为贪心也要求最优子结构，找最优子结构的方法和动态规划一样，即要找到对于一个问题，它的最优解包含了其子问题的最优解(对了，前面说要总解动态规划的，一直没总结，这类题的确很多，也很关键)。贪心性质简单讲就是一个全局最优解可以通过局部最优选择来达到，就是步步都选择当前最优的情况。
对于这道题，首先是建模，怎样读入题目的信息，我并没有把整个图都用矩阵表示，而是自建了个数据结构row，其属性包括rid(行号)，left(左边界)，right(右边界)；然后用vector把它们一个个读入的，这样既省了空间也省了时间，再用一个column数组存储每个列所占的墙数。这样的存储就已经满足我的算法了。下面是贪心部分，首先是最优子结构，设S_j 为从第0行到第j行为达满足条件而要删去的最小墙数，那么S_j=S_j-1+N_j  其中N_j为为满足第j列墙数不大于k删去的最小墙数，N_j =C_j - k (when C_j > k  ) or N_j = 0; 其中C_j为第为j列当前的墙数(即在前面j-1列删除了墙之后)。下面对N_j  加以说明，显然要使它尽可能的小就要使C_j 尽可能的小，所以在删除第j列之前的删除工作要尽量的删除右边界大的墙，也就是对于第j列选择删除墙时也要选择右边界大的墙删除得到N_j  。
我们来证明这样的S_j具有最优子结构性质，即若S_j最优S_j-1也最优。
假设S_j-1不是最优的，那设存在T<S_j-1，因为根据N_j 的选择规则其大小是一定的，所以T+N_j <S_j-1+N_j =S_j，即存在有比S_j更优的方案，这与S_j最优矛盾，所以若S_j最优S_j-1也最优的。
那么根据N_j 的选择方式就可知其满足贪心性质，每次贪心的选择右边界最大的墙删除保证当前列满足条件。
这样算法就出来了，即从下标为0的列从左到右扫描到下标最大的列，对每一列循环操作至这一列的墙数不大于k，循环中每一次操作找右边界最大的墙删除即可。
这题还有一些小细节：
1.题目可能给出的第一个列坐标比第二个大，要判断下；
2.一行可能有多个墙(这个直接影响了算法，不然会有更简单的贪心方法)。
代码如下：