#PU626. USACO 2016 February Contest, Platinum — Problem 3. Circular Barn

    ID: 1361 传统题 文件IO:cbarn 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:feb16来源:usaco.orgscoring:equal_test_cases

USACO 2016 February Contest, Platinum — Problem 3. Circular Barn

USACO 2016 February Contest, Platinum — Problem 3. Circular Barn

题目描述

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 nn rooms, numbered clockwise from 1…n1 \ldots n around the perimeter of the barn (3≤n≤1,0003 \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 rir_i cows to end up in room ii (1≤ri≤1,000,0001 \leq r_i \leq 1,000,000). To herd the cows into the barn in an orderly fashion, he plans to unlock kk exterior doors (1≤k≤71 \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 kk 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 kk such doors to unlock.

输入格式

The first line of input contains nn and kk. Each of the remaining nn lines contain r1…rnr_1 \ldots r_n.

输出格式

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

数据范围

(见题面原文)

样例

样例 1

6 2
2
5
4
2
6
2
14
Farmer John can unlock doors 2 and 5.  11 cows enter at door 2 and walk a total
distance of 8 to get to rooms 2, 3, and 4.  10 cows enter at door 5 and walk a
total distance of 6 to get to rooms 5, 6 and 1.
Problem credits: Brian Dean