Максимальная нажива

[TOTAL]

В $i$-ой куче лежит $s_i$ камней, $i=1, \cdots, n$. Если я найду кучу с номером $i,$ в которой камней больше, чем в куче с номером $i+1,$ то я перекладываю один камень из кучи $i$ в кучу $i+1.$ За такое перекладывание мне платят 1 золотую монету, поэтому я высматриваю, где бы ещё можно переложить камень. И так далее. Хочется заработать как можно больше. Предложите стратегию.

[Хорхе]

Кагбе понятно, что стратегия такая: сначала переложить все, что можно, из $n-1$ в $n$. Затем из $n-2$ в $n-1$. Затем снова из $n-1$ в $n$. Затем снова из $n-2$ в $n-1$. Когда нечего уже перекладывать, то из из $n-3$ в $n-2$. И так далее. Доказать оптимальность пока не могу.

[Simba]

Хорхе, может индукцией?
Для начала отметим, что по вашей стратегии, в итоге последняя куча имеет наибольшее(может одно из наибольших) количество камней среди всех куч, иначе нашлась куча которая имеет макс камней, т.е. мы не закончили операции, а по стратегии мы, как говорится, делаем до талого.
Допустим для k эта стратегия верна, покажем что и для k+1 она действует. Иметь монеты с k+1 кучи мы можем только перебрасывая камни с k в k+1, т.е. обеспеча маскимумом камнями k-ую кучу, мы поимеем максимум монет с k+1-ой, а применяя стратегию к первым k кучам, мы обеспечиваем максимум камнями k-ую кучу, т.е. обеспечиваем максимальную выгоду с k+1 кучи, а в совокупности со всех куч.

Верно ли? Или я ошибся?

[TOTAL]

Simba в сообщении #484307 писал(а):

Допустим для k эта стратегия верна, покажем что и для k+1 она действует.

В какую сторону она действует?
Заработать меньше, чем по этой стратегии, у меня никак не получается!