P2933 [USACO09JAN]气象测量The Baric Bovine

    • 113通过
    • 184提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 USACO 2009
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Following up on a journal article about increasing milk production, Bessie has become the Baric Bovine by studying atmospheric pressure in order to curry favor with Farmer John.

    She takes N (1 <= N <= 100) measurements conveniently named M_1 through M_N during the day (1 <= M_i <= 1,000,000); these measurements are numbered in the order in which Bessie observed them.

    In order to characterize the day's atmospheric pressure readings, she is interested in finding a subset of the measurements (given by the K (1 <= K <= N) indices s_j where 1 <= s_1 < s_2 < ... < s_K <= N) that accurately reflects the entire set, i.e., limits the error as described below.

    In any subset of measurements, an error is incurred for each

    measurement (1) before the first member of the subset, (2) between two consecutive measurements in the subset, and (3) after the last member of the subset. The total error value for a given set of s_j values is the sum of each of the individual errors.

    Specifically, for all measurements whose index i is not one of the s_j values:

    * if i is less than s_1, then the sample error is: 
    2 * | M_i - M_(s_1) | 
    * if i is between s_j and s_(j+1), then the sample error is 
    | 2 * M_i - Sum(s_j, s_(j+1)) | 
    where Sum(x, y) = M_x + M_y; 
    * if i is greater than s_K, then the sample error is 
    2 * | M_i - M_(s_K) | 
    Given a maximum error value E (1 <= E <= 1,000,000), determine the size of the smallest subset of measurements that produces an error of at most E. 

    为了研究农场的气候,Betsy帮助农夫John做了$N(1 \leq N \leq 100)$次气压测量并按顺序记录了结果$M_1 \cdots M_n(1 \leq M_i \leq 1,000,000)$. Betsy想找出一部分测量结果来总结整天的气压分布. 她想用$K(1 \leq K \leq N)$个数$s_j (1 \leq s_1 < s_2 < \cdots < s_K \leq N)$来概括所有测量结果. 她想限制如下的误差: 对于任何测量结果子集,每一个非此子集中的结果都会产生误差.总误差是所有测量结果的误差之和.更明确地说, 对于每一个和所有$s_j$都不同的$i$:

    • 如果 $i$ 小于 $s_1$, 误差是: $2 \times | M_i - M_{(s_1)} |$

    • 如果$i$在$s_j$和$s_{(j+1)}$之间,误差是: $| 2 \times M_i - Sum(s_j, s_{(j+1)}) |$ 注:$Sum(x, y) = M_x + M_y;$ ($M_x$ 和 $M_y$ 之和)

    • 如果$i$大于$s_K$,误差为: $2 \times | M_i - M_{(s_K)} |$ Besty给了最大允许的误差$E (1 \leq E \leq 1,000,000)$,找出最小的一部分结果使得误差最多为E.

    输入输出格式

    输入格式:

    * Line 1: Two space-separated integers: N and E

    * Lines 2..N+1: Line i+1 contains a single integer: M_i

    输出格式:

    * Line 1: Two space-separated integers: the size of the smallest subset of measurements that produces an error of at most E and the least possible error for the subset of that size.

    输入输出样例

    输入样例#1: 复制
    4 20 
    10 
    3 
    20 
    40 
    
    输出样例#1: 复制
    2 17 
    

    说明

    Bessie takes four measurements; the maximum error is 20. The

    measurements are, in sequence: 10, 3, 20, and 40.

    Choosing the second and fourth measurements is the best option, giving an error of 17. The first term's error is 2*|10-3| = 14; the third term's error is |2*20 - (3+40)| = 3.

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