bzoj:1575: [Usaco2009 Jan]气象牛Baric

Description

为了研究农场的气候,Betsy帮助农夫John做了N(1 <= N <= 100)次气压测量并按顺序记录了结果M_1...M_N(1 <= M_i <= 1,000,000). Betsy想找出一部分测量结果来总结整天的气压分布. 她想用K(1 <= K <= N)个数s_j (1 <= s_1 < s_2 < ... < s_K <= N)来概括所有测量结果. 她想限制如下的误差: 对于任何测量结果子集,每一个非此子集中的结果都会产生误差.总误差是所有测量结果的误差之和.更明确第说, 对于每一个和所有s_j都不同的i: * 如果 i 小于 s_1, 误差是: 2 * | M_i - M_(s_1) | * 如果i在s_j和s_(j+1)之间,误差是: | 2 * M_i - Sum(s_j, s_(j+1)) | 注:Sum(x, y) = M_x + M_y; (M_x 和 M_y 之和) * 如果i大于s_K,误差为: 2 * | M_i - M_(s_K) | Besty给了最大允许的误差E (1 <= E <= 1,000,000),找出最小的一部分结果史得误差最多为E.

Input

* 第一行: 两个空格分离的数: N 和 E

 * 第2..N+1行: 第i+1行包含一次测量记录:M_i

Output

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

Sample Input

4 20
10
3
20
40

输入解释:

Bessie做了4次记录,分别为10,3,20,和40.最大允许误差是20.

Sample Output

2 17

 

 

初二打noip普及组模拟赛的时候切过这题……

dp[i][j]表示前i个数拿出了j个数，并且第i个数必定取到的最小误差。

#include<queue>
#include<cstdio>
#include<algorithm>
#define MN 102
using namespace std;
int read_p,read_ca,read_f;
inline int read(){
    read_p=0;read_ca=getchar();read_f=1;
    while(read_ca<'0'||read_ca>'9') read_f=read_ca=='-'?-1:read_f,read_ca=getchar();
    while(read_ca>='0'&&read_ca<='9') read_p=read_p*10+read_ca-48,read_ca=getchar();
    return read_p*read_f;
}

int n,m,a[MN],mmh[MN][MN],C[MN][MN],q[MN],MMH=1e9,Mavis;
inline int abs(int x){return x>0?x:-x;}
inline void MIN(int &x,int y){if(x>y)x=y;}
int main(){
    register int i,j,k;
    n=read();m=read();
    for (i=1;i<=n;i++) a[i]=read();
    
    for (i=1;i<=n;i++)
    for (j=i+1;j<=n;j++)
    for (k=i+1;k<j;k++) C[i][j]+=abs(a[k]+a[k]-a[i]-a[j]);
    
    for (i=1;i<=n;i++)
    for (j=1;j<i;j++) mmh[i][1]+=abs(a[i]-a[j])<<1;
    
    for (i=1;i<=n;i++)
    for (j=i+1;j<=n;j++) q[i]+=abs(a[i]-a[j])<<1;
    
    for (i=1;i<=n;i++)
    for (j=2;j<=i;j++)
    for (mmh[i][j]=1e9,k=j-1;k<i;k++) MIN(mmh[i][j],mmh[k][j-1]+C[k][i]);
    
    for (i=1;i<=n;i++)
    for (j=1;j<=i&&j<=MMH;j++)
    if (mmh[i][j]+q[i]<m)
    if (j<MMH) MMH=j,Mavis=mmh[i][j]+q[i];else if (j==MMH&&Mavis>mmh[i][j]+q[i]) Mavis=mmh[i][j]+q[i];
    
    printf("%d %d
",MMH,Mavis);
}