#P1575. [Usaco2009 Jan]气象牛Baric

[Usaco2009 Jan]气象牛Baric

题目描述

为了研究农场的气候, Betsy 帮助 FJ 做了 nn 次气压测量并按顺序记录了结果 mim_i(1≤i≤n1\leq i\leq n)。Betsy 想找出一部分测量结果来总结整天的气压分布。她想用 kk 个数 sjs_j(1≤j≤k1\leq j\leq k)来概括所有测量结果。她想限制如下的误差:对于任何测量结果子集,每一个非此子集中的结果都会产生误差。总误差是所有测量结果的误差之和。更明确地说,对于每一个和所有 sjs_j 都不同的 ii:

  • 如果 i<s1i < s_1,误差是 2⋅∣mi−ms1∣2\cdot \left| m_i - m_{s_1} \right|。
  • 如果 sj≤i≤sj+1s_j\leq i \leq s_{j+1},误差是 ∣2⋅mi−msj−msj−1∣\left| 2 \cdot m_i - m_{s_j} - m_{s_{j-1}} \right|。
  • 如果 i>ski > s_k,误差是 2⋅∣mi−msk∣2 \cdot | m_i - m_{s_k} |。

Besty 给了最大允许的误差 ee,找出最小的一部分结果使得误差最多为 ee。

输入格式

第一行:两个空格分隔的数: nn 和 ee。

第 2∼n+12\sim n+1 行:第 i+1i+1 行包含一次测量记录:mim_i。

输出格式

  • 第一行:共两个数:最少能达到误差小于等于 ee 的测量数目和使用那个测量数目能达到的最小误差。
4 20
10
3
20
40
2 17

数据规模与约定

对于 100%100\% 的数据,1≤n≤1001 \leq n \leq 100,1≤mi≤1×1061 \leq m_i \leq 1\times 10^6,1≤k≤n1 \leq k \leq n,1≤s1<s2<...<sk≤n1 \leq s_1 < s_2 < ... < s_k \leq n,1≤e≤1×1061 \leq e \leq 1\times 10^{6}。

提示

Bessie 做了 44 次记录,分别为 1010,33,2020,4040 .最大允许误差是 2020,选择第二和第四次测量结果能达到最小误差 1717。第一次结果的误差是2×∣10−3∣=142\times\left|10-3\right| = 14,第三次结果的误差是∣2×20−(3+40)∣=3\left|2\times20 - (3+40)\right|=3。

题目来源

Usaco 2009 Jan Gold