P2248 分段

    • 13通过
    • 188提交
  • 题目提供者fjzzq2002
  • 标签 O2优化 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1s / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目描述

    给定你n个数$a_1、a_2、a_3、...、a_n$,要求将它们分成若干连续的段。

    要求:

    1. 有m对给定的数不能被分到同一段。

    2. 分出一个段的代价是$K + S \times (P - Q)$,其中K和S均为给定的常数,而P则是该段中所有数的最大值,Q是该段中所有数的最小值。

    3. 要求你求出每段代价之和最小的分段方案。

    输入输出格式

    输入格式:

    第一行两个正整数n和m,表示数的个数和不能共存的m对数。

    第二行两个非负整数K和S,含义见题面。

    第三行n个非负整数,即给定的n个数。

    接下来m行每行2个数$p_i$和$q_i$,表示$p_i$和$q_i$这两个编号的数不能共存。(编号从1开始)

    输出格式:

    输出仅一行,表示最小的每段代价之和。

    输入输出样例

    输入样例#1: 复制
    5 2
    3 1
    2 3 12 14 16
    2 3
    3 1
    输出样例#1: 复制
    11

    说明

    对于10%的数据,$n \leq 10$;

    对于30%的数据,$n \leq 1500$;

    对于另外10%的数据,$S = 0$;

    对于另外30%的数据,$m = 0$;

    对于100%的数据,1≤m,n≤100000,0≤K,S,a_i≤100000,1≤pi,qi≤n,pi≠qi。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。