早知道早点敲博赚访问量
Description
小H是机场登机的执行经理。他的工作是优化登机流程。飞机上的座位有S行,编号从1到s,每行有六个座位,标记为A到F。
今天 有n个乘客陆续登机,第i名乘客的座位在第Ri行,则第i名乘客的登机难度等于在他登机时坐在1…R(i-1)行的乘客的人数。
例如,如果有10名乘客,他们的座位是6A,4B,2E,5F,2A,3F,1C,10E,8B,5A,那么他们的登机困难分别是0,0,0,2,0,2,0,7,7,5,则难度总和为23 。
为了降低登机难度,小H想要将飞机座位划分为k个区域。每一个区域必须是连续的行。划分成k个区域之后,乘客的登机顺序不会改变,但是每个乘客的登机难度将只统计该乘客所在区域前面乘客的人数。
例如,在上面的例子中,如果我们把该平面分成两个区域: 5-10行和1-4行 ,然后在第一区域中的乘客的座位为6A,5F,10E,8B,5A;在第二区域中的乘客的座位为4B,2E,2A,3F,1C,这种情况下,登机难度综合为6。
现在,小H不知道该怎么划分这k个区域,才能让乘客的登机难度总和最少。
Input
输入文件第一行包含三个整数N,S,和k,下一行包含n个整数(1≤Ri≤S),输入保证每一行座位由最多有6名乘客。
Output
输出文件包含一个整数,表示登机可能的最小登机难度。
Sample Input
10 12 2
6 4 2 5 2 3 1 11 8 5
Sample Output
6
Data Constraint
40%的数据,n<=100,s<=100
100%的数据,n<=1000,s<=1000, k<=50, k<=s
看着醉人的数据范围,DP无疑
变量解释