LARMY - Lannister Army
题意翻译
### 题目描述
“Lannister 有债必还。”现在你有机会得到 Jaime Lannister 的报酬了。
在 Jamie 的军队里共有 $N$ 名战士站成一行。
现在 Jamie 想向他的战士们传达一条信息。但是如果战士们全部站在一行中，消息传递是很困难的。
所以 Jaime 想把战士们分成 $K$ 行。每行至少要有一个战士。
设第 $i$ 行第 $j$ 个战士的身高为 $h_{i,j}$。定义第 $i$ 行第 $j$ 个战士的**不快乐度**为在第 $i$ 行的编号小于 $j$ 的战士中，身高高于他的战士的数量。形式化地说，就是 $\sum_{k=1}^{j-1} [h_{i,k}\gt h_{i,j}]$。特别地，每行的第一个战士的不快乐度为 $0$。
战士们开心了，才能打好仗。Jaime 想让你求出分成 $K$ 行后的战士们不快乐度之和最小是多少。
注意：**不允许交换两名战士的顺序。**
### 输入格式
输入的第一行包含两个正整数 $N$，$K$，含义见题面。
第二行输入包含 $N$ 个正整数，其中第 $i$ 个数表示第 $i$ 个战士的身高 $h_i$。
### 输出格式
输出一行一个整数，即不快乐度之和的最小值。
### 样例 1
```
8 3
20 50 30 60 40 100 5 1
```
```
2
```
### 数据范围与提示
样例中，一个最优解为
```
20,50,30,60;
40,100;
5,1;
```
$1\le K\le N\le 5000$，$1\le h_i\le 10^5$。
$\text{Statement fixed by @Starrykiller.}$
题目描述
_"A Lannister Always Pays His Debts."_
That's true, now here is a chance for you to get paid by Jaime Lannister.
In Jaime's army there are total **N** number of warriors.
And all them are standing in a single row.
Now Jaime wants to convey a message to his warriors. But it's very difficult to convey a message if warriors are standing in a single row.
So, Jaime wants to break that single row into **K** rows. Such that in each row at least one warriors should be there.
Also, there is an amount of unhappiness associated with each warrior x which is equal to : number of warriors in front of x (in his row) whose height is greater than the height of x. And, total unhappiness is sum of unhappiness of all warriors. Jaime wants that his army should be happy as much as possible.
Now, Jaime wants you to break the single row into **K** rows such that total unhappiness should be minimum.
**Note** : You just have to break the row, you are not allowed to change the position of the warriors.
**Input Format**
First line of input contain two integers **N** & **K**.
Second line of input contain **N** number of integers, **i** th of which denote height of **i** th warrior standing in that single row (represented as **H\[i\]**).
**Constraints**
1 <= **N** <= 5000
1 <= **K** <= N
1 <= **H\[i\]** <= 10^5
**Output Format**
Output the minimum possible value of "total unhappiness".
**Examples**
**Input**
6 3
20 50 30 60 40 100
**Output**
0
**Explanation**
Break as :
Row 1 : 20 50
Row 2 : 30 60
Row 3 : 40 100
**Input**
8 3
20 50 30 60 40 100 5 1
**Output**
2
**Explanation**
Row 1 : 20 50 30 60, Unhappiness = 1
Row 2 : 40 100, Unhappiness = 0
Row 3 : 5 1, Unhappiness = 1
Total = 2