Being a fan of contemporary architecture, Farmer John has built a new barn in
the shape of a perfect circle. Inside, the barn consists of a ring of \(n\)
rooms, numbered clockwise from \(1 \ldots n\) around the perimeter of the barn
(\(3 \leq n \leq 1,000\)). Each room has doors to its two neighboring rooms, and
also a door opening to the exterior of the barn.

Farmer John wants exactly \(r_i\) cows to end up in room \(i\)
(\(1 \leq r_i \leq 1,000,000\)). To herd the cows into the barn in an orderly
fashion, he plans to unlock \(k\) exterior doors (\(1 \leq k \leq 7\)), allowing the
cows to enter through only those doors. Each cow then walks clockwise through
the rooms until she reaches a suitable destination. Farmer John wants to unlock
the exterior doors that will cause his cows to collectively walk a minimum total
amount of distance after entering the barn (they can initially line up however
they like outside the \(k\) unlocked doors; this does not contribute to the total
distance in question). Please determine the minimum total distance his cows
will need to walk, if he chooses the best \(k\) such doors to unlock.

Problem credits: Brian Dean

Problem credits: Brian Dean

The first line of input contains \(n\) and \(k\). Each of the remaining \(n\) lines
contain \(r_1 \ldots r_n\).

Please write out the minimum amount of distance the cows need to travel.

riseoj 작성

출처 올림피아드 > USACO > 2015-2016 > February > Platinum