TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3738
  • 题目
  • P3738学号管理
    限制 : 时间限制 : - MS   空间限制 : 65536 KB
    评测说明 : 时限1000ms
    问题描述

       南开中学信竞班有N名同学,为方便管理,何老板给每个同学设置了一个学号(1到N之间的一个整数)。
       今天,何老板发现,因为他的疏忽,某些同学的学号是相同的。他想将部分同学的学号做一下修改,使得N个同学的学号恰好构成一个1到N的排列。
       但很多同学并不买账,他们不想轻易修改自己的学号。经过讨价还价,每个同学都希望修改后的学号与原学号近可能相近,每个同学都给出了一个他能接受的学号范围[A,B],如果超出他能接受的范围,他就会拒绝修改。每个同学还向何老板提出了一个修改代价V,比如何老板将第i个同学的学号从Xi改成了Xi'(Ai<=Xi'<=Bi),那么他需要提供给这位同学Vi*|Xi'-Xi|小时的合法游戏时间。在这段时间内该同学打游戏,何老板不得干涉他。
       何老板希望能使得所有同学的学号恰好是1到N,但又希望同学们合法玩游戏的总时间尽可能少,问是否能满足何老板的要求。能输出最少游戏总时间,否则输出NO

    输入格式

    第一行,一个整数N,表示学生人数。
    接下来N行,每行四个整数,描述一个学生。第i行为Xi,Ai,Bi,Vi,分别表示第i个同学现在的学号,他期望的新学号所在区间[Ai,Bi],和修改代价

    输出格式

    一行,一个整数表示答案。如果无解,输出NO

    样例输入 1

    5
    1 1 2 3
    1 1 5 1
    3 2 5 5
    4 1 5 10
    3 3 3 1

    样例输出 1

    9

    样例输入 2

    10
    1 1 5 5
    1 1 4 4
    1 1 3 3
    1 1 2 2
    1 1 1 1
    10 10 10 1
    10 9 10 2
    10 8 10 3
    10 7 10 4
    10 6 10 5

    样例输出 2

    80

    提示

    1<=N<=200
    1<=Ai<=Xi<=Bi<=N
    1<=Vi<=1000


    来源  改编自POI 2006 Szk-Schools