TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P4123
  • 题目
  • P4123佛罗里达
    限制 : 时间限制 : 30000 MS   空间限制 : 262144 KB
    评测说明 : 3S,256M
    问题描述

    没有得到激光武器的苏联十分生气,他们决定派遣一支特种部队强行 登陆美国并造成一定的袭击。 Reddington 得到的情报是他们将在佛罗里达
    海岸登陆,他决定派遣他的手下去阻击他们。可惜的是, Reddington 由于 不听从总统的意见,手中的部队只剩下了 N
    个人。人与人之间会有一定的 矛盾值,第 i 个人与第 j 个人的矛盾值为 Ti,j,并且有 Ti,i = 0, Ti,j = Tj,i。
    Reddington 希望将这 N 个人分为两支小分队,记为 A, B,每个人要么属 于分队 A 要么属于分队 B。对于一支小分队
    S,其内部的不安值
    在这里插入图片描述
    显然的,假如一支分队的不安值很高,那么作战能力就会很差。现在 给定你 N 以及一个 N ∗ N 的矩阵 T,你需要告诉
    Reddington,最小的 D(A) + D(B) 是多少。

    输入格式

    输入包括多组数据。
    对于每组数据: 第一行一个整数 N。
    接下来 N −1 行,第 i 行读入 N −i 个数,第 i 行第 j 个数表示 Ti,i+j。
    $2 ≤ N ≤ 250, 0 ≤ Ti,j ≤ 10^9$,数据组数不超过 2 组

    输出格式

    一行,最小的 D(A) + D(B) 是多少

    样例输入

    5
    4 5 0 2
    1 3 7
    2 0
    4

    样例输出

    4

    提示

    //一种最优方案为: A = {1, 2, 4}, B = {3, 5},此时 D(A) = 4, D(B) =0


    来源  bzoj4670