TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P6472
  • 题目
  • P6472幻龙偷猪
    限制 : 时间限制 : 10000 MS   空间限制 : 565536 KB
    评测说明 : 1s,512m
    问题描述

    何老板在农场上养了n头猪,编号1到n,其中第i头猪的坐标为(Xi,Yi),第i头猪的体重为Vi,猪们很乖,它们不会移动位置。(我们可以把农场看作二维平面)。

    幻龙想要偷走一些猪。
    要从何老板那里偷猪是一件非常困难的事情,有m个条件(编号1到m)需要满足,每个条件都是下面四种描述之一:
    ti='L',ai,bi:幻龙最多能从x坐标小于等于ai的猪中偷走bi只;
    ti='R',ai,bi:幻龙最多能从x坐标大于等于ai的猪中偷走bi只;
    ti='D',ai,bi:幻龙最多能从y坐标小于等于ai的猪中偷走bi只;
    ti='U',ai,bi:幻龙最多能从y坐标大于等于ai的猪中偷走bi只;

    问,幻龙能偷走的猪的最大重量总和。

    输入格式

    第一行,一个整数n
    接下来n行,每行三个整数Xi,Yi,Vi描述一头猪的信息
    接下来一行,一个整数m 接下来m行,每行三个整数ti,ai,bi描述一个条件。

    输出格式

    一个整数,表示能偷到的最大总重

    样例输入 1

    7
    1 3 6
    1 5 9
    3 1 8
    4 3 8
    6 2 9
    5 4 11
    5 7 10
    4
    L 3 1
    R 2 3
    D 5 3
    U 4 2

    样例输出 1

    36

    样例输入 2

    3
    1 2 3
    4 5 6
    7 8 9
    1
    L 100 0

    样例输出 2

    0

    样例输入 3

    4
    1 1 10
    1 2 11
    2 1 12
    2 2 13
    3
    L 8 3
    L 9 2
    L 10 1

    样例输出 3

    13

    样例输入 4

    10
    66 47 71040136000
    65 77 74799603000
    80 53 91192869000
    24 34 24931901000
    91 78 49867703000
    68 71 46108236000
    46 73 74799603000
    56 63 93122668000
    32 51 71030136000
    51 26 70912345000
    21
    L 51 1
    L 7 0
    U 47 4
    R 92 0
    R 91 1
    D 53 2
    R 65 3
    D 13 0
    U 63 3
    L 68 3
    D 47 1
    L 91 5
    R 32 4
    L 66 2
    L 80 4
    D 77 4
    U 73 1
    D 78 5
    U 26 5
    R 80 2
    R 24 5

    样例输出 4

    305223377000

    提示
  • $ 1 \leq N \leq 80 $
  • $ 1 \leq x_i, y_i \leq 100 $
  • $ 1 \leq v_i \leq 10^{15} $
  • $ 1 \leq M \leq 320 $
  • $ 1 \leq a_i \leq 100 $
  • $ 0 \leq b_i \leq N - 1 $
  • $ (x_i, y_i) $ 不会有重复.
  • $ (t_i, a_i) $ 不会有重复.
  • $ (t_i, b_i) $ 不会有重复.

  • 来源  AGC031E