TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P2633
  • 题目
  • P2633【ZJOI2013 DAY1】防守战线
    限制 : 时间限制 : 20000 MS   空间限制 : 565536 KB
    问题描述

    战线可以看作一个长度为n 的序列,现在需要在这个序列上建塔来防守敌兵,在序列第i 号位置上建一座塔有Ci 的花费,且一个位置可以建任意多的塔,费用累加计算。有m 个区间[L1, R1], [L2, R2], …, [Lm, Rm],在第i 个区间的范围内要建至少Di 座塔。求最少花费。

    输入格式

    第一行为两个数n, m。
    接下来一行,有n 个数,描述C 数组。
    接下来m 行,每行三个数Li,Ri,Di,描述一个区间。

    输出格式

    仅包含一行,一个数,为最少花费。

    样例输入

    5 3
    1 5 6 3 4
    2 3 1
    1 5 4
    3 5 2

    样例输出

    11

    提示

    【样例说明】
    位置1 建2 个塔,位置3 建一个塔,位置4 建一个塔。花费1*2+6+3=11。
    【数据规模】
    对于20%的数据,n≤20,m≤20。
    对于50%的数据(包括上部分的数据),Di 全部为1。
    对于70%的数据(包括上部分的数据),n≤100,m≤1000。
    对于100%的数据,n≤1000,m≤10000,1≤Li≤Ri≤n,其余数据均≤10000。