HDU 1300 - Pearls
Problem : Given n items, each need number of a[i] and cost b[i] for each. (a[1]<a[2]<...<a[n]). The cost for each type is (number of buy+10)*b[i] if number of buy > 0. However, the type i item can be upgrade to same number of type j if j>i. Calculate the minimum cost to meet the requirement.
Solution : Denote f[i] to be the first i type's total cost when the i-th type is buied. then f[i]=min{f[j]+cost(type j to i are all upgrade to i) | j<i}.
Proof : reduction.