2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2, 3
 
 
Сообщение04.04.2011, 17:39 
Аватара пользователя
Решение понятно, спасибо всем. Но вот, что написал mserg не совсем понял, Вы можете как-то более формально описать?)

 
 
 
 
Сообщение04.04.2011, 22:06 
Да он всё вполне формально описал, разве что не везде вполне аккуратно.

Пункт 1-й: если все члены ненулевые, то можно увеличить ту сумму произведений, сделав один из членов нулевым, перекинув его значение на соседнее (через один). Это -- наименее тривиальный момент; ну уж с этим сами разберитесь.

Остальное -- уже достаточно очевидно.

Пункт второй: если есть хотя бы один ноль, то все нули можно сосредоточить на сплошном участке (поскольку перемещение какого-либо нуля, не находившегося на этом участке, на тот самый участок -- ту сумму произведений как минимум не уменьшит).

Пункт третий. После того, как у нас есть два сплошных участка: состоящий из нулей и из ненулей -- мы можем потихонечку откусывать по одному элементу ненулевого участка с любого его конца, сокращая при этом его длину и заведомо не уменьшая при этом сумму произведений.

Вот так в конце концов и придём к всего лишь трём подряд идущим ненулевым членам.

Правда, насчёт единственности полученной максимальной конфигурации -- придётся ещё чуток попыхтеть; но не очень сильно.

 
 
 [ Сообщений: 32 ]  На страницу Пред.  1, 2, 3


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group