问题 23810 --测绘

23810: 测绘

时间限制: 1 Sec  内存限制: 128 MB
提交: 56  解决: 12
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][92kb]

题目描述

       为了研究农场的气候,Betsy帮助农夫John做了N(1≤N≤100)次气压测量并按顺序记录了结果M1,M2,…,MN(1≤Mi≤1,000,000).
Betsy想找出一部分测量结果来总结整天的气压分布. 她想用K(1≤K≤N)个数sj(1≤s1<s2<…<sK≤N)来概括所有测量结果. 她想限制如下的误差:
对于任何测量结果子集,每一个非此子集中的结果都会产生误差.总误差是所有测量结果的误差之和.更明确第说, 对于每一个和所有sj都不同的i:
* 如果 i 小于 s1, 误差是: 2*|Mi–M(s1)|
* 如果i在sj和s(j+1)之间,误差是: |2*Mi–Sum(sj,s(j+1))|
注:Sum(x,y)=Mx+My; (Mx 和 My 之和)
* 如果i大于sK,误差为: 2*|Mi–M(sK)|
Besty给了最大允许的误差E(1≤E≤1,000,000),找出最小的一部分结果使得误差最多为E.

输入

* 第一行: 两个空格分离的数: N 和 E
* 第2..N+1行: 第i+1行包含一次测量记录:M_i

输出

第一行: 两个空格分开的数: 最少能达到误差小于等于E的测量数目和使用那个测量
数目能达到的最小误差.

样例输入

4 20
10
3
20
40

样例输出

2 17

提示

样例说明:

选择第二次和第四次的测量结果能达到最小误差17.

来源

[提交][状态]