HDU 1692 - Destroy the Well of Life
Problem : N towers. Each tower has a[i] energy. You can destroy the tower by cost c[i] mana or let the energy of that tower more than b[i]. When tower is destroied, all the energy it has will push to i+1-th tower. Now it's needed to destroy the n-th tower, get the minimum mana cost to achieve it.
Solution :
1) If there is a solution, s.t. the i, i+1, ..., j-1, j+1, j+2, ..., n-th tower is destroied. Just destroy j+1, j+2, ..., n-th tower will cost less mana. Since if j-th tower is not destoried, to destroy j+1 to n-th tower cost exactly the same mana as avoid destroying i to j-1-th tower. Meanwhile, to destroy tower from i to j-1-th will need at least the i-th tower's mana cost. Hence, we only need to consider the cost of starting from i-th tower, destroy all the way to the n-th tower, and get one of the minimum cost of i.

2) Denote the value g[i] is the tower id s.t. if destroy from g[i], tower i needn't destory by mana. Denote f[i] to be the cost start from tower i, destroy all the way to the tower n. Then f[i]=f[i+1]+c[i]-sum{ c[j] | g[j]=i }. Get g need O(nlogn) time, Get f only need O(n) time (with using link list to record all the g[j]=i). The total time is O(nlogn).