Форум Всеукраїнської інтернет-олімпіади NetOI

вот заполненный массив

 8   24   12    6    7    1 
32   36   18   13    8 
36   36   18   13 
42   36   18 
42   36 
42 

буду обозначать G(a b c) - время на исследование отрезка a b c

если пробурить 8 и нефть там есть (худший случай), придется потратить дополнительно G(24   12    6    7    1)=34. 8+36=44.
если пробурить первой 24, тогда либо 8, либо G(12    6    7    1 )=18. худший случай 24+18=42.
вывод: начинать бурение МОЖНО с точки 24, потому что в этом случае НАВЕРНЯКА уложимся в оптимальное время 42.

итак G(8   24   12    6    7    1 ) = 24 + G(12    6    7    1 )

рассмотрим теперь 12    6    7    1 
если начать в 12: 12+G(6    7    1 )=12+13=25>18 - не то
если начать в 6: 6+max(12,G(7    1))=6+12=18 - значит следующей бурить МОЖНО точку 6

осталась только точка 12.

значит G(8   24   12    6    7    1 ) = 24 + 6 + 12 = 42

вот вам план бурения, который определит где заканчивается нефть за время не большее 42 как нефть ни изворачивайся (худший случай)