Ciel and Gondolas

题意翻译

## 题意： Ciel狐狸在游乐园里排队等待上摩天轮。现在有$n$ 个人在队列里，有$k$ 条船，第i条船到时，前$q_{i}$ 个人可以上船。最后一条船将载走剩下的所有人，则$q_{k}$ 此时载走的人数。 人总是不愿意和陌生人上同一条船的，当第$i$ 个人与第$j$ 个人处于同一条船上时，会产生$u_{i,j}$ 的沮丧值。请你求出最小的沮丧值和。 一条船上的人两两都会产生沮丧值。 ##### 输入格式： 第一行两个数代表$n$ ,$k$ ，接下来$n$ 行每行$n$ 个数，第$i$ 行第$j$ 个数表示$u_{i,j}$ 。 请使用快速读入的技巧，防止读入导致的TLE。 ##### 输出格式： 一行一个整数表示最小沮丧值。 贡献者：MSF_Akatsuki

题目描述

Fox Ciel is in the Amusement Park. And now she is in a queue in front of the Ferris wheel. There are $ n $ people (or foxes more precisely) in the queue: we use first people to refer one at the head of the queue, and $ n $ -th people to refer the last one in the queue. There will be $ k $ gondolas, and the way we allocate gondolas looks like this: - When the first gondolas come, the $ q_{1} $ people in head of the queue go into the gondolas. - Then when the second gondolas come, the $ q_{2} $ people in head of the remain queue go into the gondolas. ... - The remain $ q_{k} $ people go into the last ( $ k $ -th) gondolas. Note that $ q_{1} $ , $ q_{2} $ , ..., $ q_{k} $ must be positive. You can get from the statement that  and $ q_{i}>0 $ . You know, people don't want to stay with strangers in the gondolas, so your task is to find an optimal allocation way (that is find an optimal sequence $ q $ ) to make people happy. For every pair of people $ i $ and $ j $ , there exists a value $ u_{ij} $ denotes a level of unfamiliar. You can assume $ u_{ij}=u_{ji} $ for all $ i,j $ $ (1<=i,j<=n) $ and $ u_{ii}=0 $ for all $ i $ $ (1<=i<=n) $ . Then an unfamiliar value of a gondolas is the sum of the levels of unfamiliar between any pair of people that is into the gondolas. A total unfamiliar value is the sum of unfamiliar values for all gondolas. Help Fox Ciel to find the minimal possible total unfamiliar value for some optimal allocation.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ k $ ( $ 1<=n<=4000 $ and $ 1<=k<=min(n,800) $ ) — the number of people in the queue and the number of gondolas. Each of the following $ n $ lines contains $ n $ integers — matrix $ u $ , ( $ 0<=u_{ij}<=9 $ , $ u_{ij}=u_{ji} $ and $ u_{ii}=0 $ ). Please, use fast input methods (for example, please use BufferedReader instead of Scanner for Java).

输出格式

Print an integer — the minimal possible total unfamiliar value.

输入输出样例

输入样例 #1

5 2
0 0 1 1 1
0 0 1 1 1
1 1 0 0 0
1 1 0 0 0
1 1 0 0 0

输出样例 #1

0

输入样例 #2

8 3
0 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1
1 1 0 1 1 1 1 1
1 1 1 0 1 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 1
1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 0

输出样例 #2

7

输入样例 #3

3 2
0 2 0
2 0 3
0 3 0

输出样例 #3

2

说明

In the first example, we can allocate people like this: {1, 2} goes into a gondolas, {3, 4, 5} goes into another gondolas. In the second example, an optimal solution is : {1, 2, 3} | {4, 5, 6} | {7, 8}.