Educational Codeforces Round71 1207C

  |  
 阅读次数

这题可以贪心解决的说。
观察可以发现,可能有效的操作是,我们把一整片高度为1的管道全部拔高为2使得这片高度为1的点和两边高度相等从而减少之字形中额外消耗的竖条。我们记这片高度为1的管道的长度为len,显然,它有len+1len+1个支撑物。这样做,拔高消耗的代价为b(len1)b* (len-1),减少消耗的代价为2a2a。每一片的拔高决策是相互独立的,因此只需要比较其大小取较小的一个即可。

expand all