题目：51
分析：原型是bzoj 1150（CTSC 2007）
首先DP无法下手，想到贪心。想到贪心的第一感觉就是从大的开始取，但明显有反例，最烦的就是一个大的旁边旁边两个也很大，导致如果取了那两个最后结果更大。解决的办法就是每次取最大的同时，把它同旁边两个点合并成一个点，权值取：左+右-中间，然后后面继续去最大的点这么做下去……
大概的认识就是给了一个反悔的机会，如果取了一个合并点也就相当于不取那个中间而取两边……
什么要我严谨证明~！
我会说神犇已经弄出原理了吗~~~哼~~~~
本文共 295 字，大约阅读时间需要 1 分钟。
题目：51
分析：原型是bzoj 1150（CTSC 2007）
首先DP无法下手，想到贪心。想到贪心的第一感觉就是从大的开始取，但明显有反例，最烦的就是一个大的旁边旁边两个也很大，导致如果取了那两个最后结果更大。解决的办法就是每次取最大的同时，把它同旁边两个点合并成一个点，权值取：左+右-中间，然后后面继续去最大的点这么做下去……
大概的认识就是给了一个反悔的机会，如果取了一个合并点也就相当于不取那个中间而取两边……
什么要我严谨证明~！
我会说神犇已经弄出原理了吗~~~哼~~~~
转载于:https://www.cnblogs.com/wmrv587/p/3879560.html