F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 5311. -- 贞鱼

5311: 贞鱼

Time Limit: 3 Sec  Memory Limit: 162 MB
Submit: 440  Solved: 108
[Submit][Status][Discuss]

Description

众所周知,贞鱼是一种高智商水生动物。不过他们到了陆地上智商会减半。
这不?他们遇到了大麻烦!
n只贞鱼到陆地上乘车,现在有k辆汽车可以租用。
由于贞鱼们并不能在陆地上自由行走,一辆车只能载一段连续的贞鱼。
贞鱼们互相有着深深的怨念,每一对贞鱼之间有怨气值。
第i只贞鱼与第j只贞鱼的怨气值记为Yij,且Yij=Yji,Yii=0。
每辆车载重不限,但是每一对在同辆车中的贞鱼都会产生怨气值。
当然,超级贞鱼zzp长者希望怨气值的总和最小。
不过他智商已经减半,想不出分配方案。
他现在找到了你,请你帮助他分配贞鱼们,并输出最小怨气值之和ans。

Input

第一行两个整数:n,k。
接下来读入一个n行n列的矩阵。矩阵中第i行j列的元素表示Yij
当然这个矩阵是对称的。

Output

一个整数ans,表示:最小的怨气值之和
★注意:同辆车中,贞鱼i,j之间的怨气只算一次!
1 ≤ n ≤4000 ,1 ≤ k ≤min(n , 800) , 0 ≤ Yij≤10 

Sample Input

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

Sample Output

7
编号为1,2,3的贞鱼一辆车:怨气值和为3;
编号为4,5,6的贞鱼一辆车:怨气值和为3;
编号为7,8的贞鱼一辆车:怨气值和为1。
最小怨气值总和为 3 + 3 + 1 = 7 。

HINT

Source

[Submit][Status][Discuss]

HOME Back