View the problem at POJ. It’s a problem from a contest in Northwestern Europe, 2002.
This is a classical DynamicPrograming problem. The sate transformation equation is:
1


f(i)
means the lowest possible price needed to buy pearls from class 1 to class i
;
a(i)
means the number of pearls needed to buy in class i
;
p(i)
menas the price of each peal in class i
;
c
means the number of categories.
The initial condition is:
1


The answer to this problem is:
f(c)
You can iteratively calculate f(i)
, ie from f(1)
to f(c)
, or recursively calculate f(i)
, with recording which f(i)
has been calculated.
If you want to prove the correctness of the state transformation, continue to the following parts.
All pearls in the same class should be bought in a unit. Prove: Assume we break them into two parts, and buy one part in class
i
, and buy another in classj
. Without lost of generous, leti < j
, if we buy all of them in classi
, we will pay less money. So this is not the best plan, and we should buy all pearls in the same class in one class.If we buy pearls, which is originally in class
i
, in a higher classj
, then we must buy all pearls originally in classk (i < k < j)
in classj
. Prove: Assume there exists some pearls in class k (i < k < j) that is not bought in classj
. Then they must be bought in classk
, or in classp (k< p < j)
, or in classq (q > j)
. If they are bought in classk
, then if the pearls in classi
are bought in classk
, we will pay less money. So this is not a best plan. If they are bought in classq
, then if they are bought in classj
, we will pay less money, so this is not an optimistic plan, either. If they are bought in classp
, then there exists some pearls in classp (k < p < j)
that is not bought in classj
, and then we replacei
withk
replacek
withp
, we get the same proposition as the original proposition. Iteratively prove this proposition, and finally this case will falls into one of the above two cases. (Becausep
is monotone increasing andj
is a limited number, so it’s convergence.) As all above cases results a contradiction, the assume is not true. Hence it is proved.
Source Code to resolve this problem:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 
