codevs 1063 合并果子

中午一看到这题，马上想起了能量项链的那个模型，即区间型的DP，完全没有注意到n的范围，犯了先入为主的错误 下午回到学校马上就去写这个几乎是模板的代码，提交直接MLE，才发现n的最大值为10000，dp[n][n】的大小为 10000 * 10000 * 4 Bytes（一个int为32 = 4 * 9 bits，即4个字节）= 400 000 KB > 题目要求的128 000KB， 因为平时我敲算法之前都没有去考虑一下这个空间复杂度是否可行，记下这次的错误，以后写算法之前要坚持先分析时间复杂度，空间复杂度，并注释在行首，以此来提醒自己思考：这个算法在要求的时间和空间下是否可以满足需求。 那么在传统的区间型DP无法解决的情况下，我又尝试了一个错误的方法，错误原因是没有考虑到 a , b ,c ,d可能是ab ,cd 划分的，并不是每次只处理1，n这样的。然后发现还有要用区间来得到一个dp的数值才行，所以陷入了思维困境。然后再翻翻STL，有没有什么数据结构可以用2个元素定位一个数，然后用完一轮之后再清掉呢？似乎也找不到。于是去看了题解。 看了题解之后我发现自己真的崩了。题目其实并没有说明一定要相邻的2堆果子才能合并在一起，只是我自己一看到合并就想起了那个区间动态的模型。所以这是我自己犯下的一个大错，需要好好反思！ 所以其实直接贪心，用一个优先级队列即可，在这里自己陌生的知识点总结如下： 优先队列默认的是数据大的优先级高， 标准库默认使用元素类型的<操作符来确定它们之间的优先级关系 PRiority_queue<type> pq; 为了使得越小优先级越高（比如本题），用法应为 priority_queue<int, vector<int>, greater<int> >pq; 第二个参数为容器类型。 第二个参数为比较函数。