测绘

Descrption

为了研究农场的气候,Betsy帮助农夫John做了 (N(1≤N≤100)) 次气压测量并按顺序记录了结果(M_1,M_2,…,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_{S1}|) ；
  - 如果 (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)) ,找出样本 (k) 最小的一部分结果使得误差最多为 (E).

Input

第一行：两个数 (N,E)（含义如题）。
接下来 (N) 行每行一个数表示气压。

Output

输出一行，两个数，第一表示最小的样本数 (K)，第二个表示这 (K) 个样本的最小误差值

Sample Input

Sample Output

2 17

Hint

选择第二次和第四次的测量结果能达到最小误差(17) 。
分析：
- 看到这种题型，我们首先要考虑 (dp) ,看能不能找到最优子结构，典型的线性 (dp) 的状态定义为 (dp[i]) 表示前 (i) 个元素作为一个子问题，但选多少个数，这显然是限制条件，很容易定义 (dp[i][j]) ,表示前 (i) 个数选择 (j) 个数的最小误差。那如何转移呢？
- 首先我们要确定一个问题，就是第一维的前 (i) 是否包含第 (i) 个元素的问题，显然必须包含第 (i) 个元素，且为所选子序列的最后一个元素，即为 (S_k) ，这样我们才好转移。转移的决策就是从 (i) 往后找一个元素加入序列。
- 转移方程：(dp[i][j]=min(dp[i][j],dp[k][j-1]+?),(j-1le k<i)) 。
  - 首先我们预处理出一个数组(pre)，(pre[i][j]) 表示原序列中(M_i,M_j) 是所选子序列的相邻的两个元素，则 (i) 到 (j) 之间元素对误差的贡献，枚举 (k,(i+1le kle j-1)) ，计算(abs(2*M_k-M_i-M_j)) ，显然我们可以 (n^3) 暴力枚举预处理出此结果。
  - (pre[i][0]) 记录如果 (M_i) 作为序列第一个数，则(M_1sim M_{i-1}) 的误差之和，(pre[i][n+1]) 记录如果 (M_i) 作为所选子序列的最后一个元素，则 (M_{i+1}sim M_n) 的误差之和。
  - 所以，(?=-pre[k][n+1]+pre[i][n+1]+pre[k][i])
    - (dp[k][j-1]) 是把 (k) 当成了序列的最后一位，所以(+pre[k][n+1]) ，所以先减去，此时把 (i) 当做了最后一位，所以 (+pre[i][n+1]) ，然后加上 (M_ksim M_i) 之间的误差 (pre[k][i]) 。
- 转移方程为：(dp[i][j]=min(dp[i][j],dp[k][j-1]-pre[k][n+1]+pre[i][n+1]+pre[k][i] ),(j-1le k<i)) 。
- 显然是由选择 (i-1) 个元素的序列推导出选择 (i) 个元素的序列，所以选择了多少个元素作为阶段，为了方便推导，对 (dp[i][j]) 重新定义为：前 (j) 个元素，最后一个元素为 (j) 共选了 (i) 个元素的最小误差。
- 转移方程：(dp[i][j]=min(dp[i][j],dp[i-1][k]-pre[k][n+1]+pre[i][n+1]+pre[k][i]),(j-1le k<i)) 。
- 当前行状态只与上一行状态相关，可以用滚动数组压维。
- Code
```
#include <bits/stdc++.h>
typedef long long LL;
const int maxn=100+15;
const int inf=0x3f3f3f3f;
int n,E;
LL ans;
int a[maxn];
LL dp[maxn][maxn],pre[maxn][maxn];
void Init(){
	scanf("%d%d",&n,&E);
    for(int i=1;i<=n;i++)
    	scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){//预处理pre[i][j]
       for(int j=i+1;j<=n;j++)
           for(int k=i+1;k<=j-1;k++)
               pre[i][j]+=abs(2*a[k]-a[i]-a[j]);
        for(int j=1;j<i;j++) pre[i][0]+=2*abs(a[j]-a[i]);//i之前
        for(int j=i+1;j<=n;j++) pre[i][n+1]+=2*abs(a[j]-a[i]);//i之后
    }
}
void Solve(){
	int id=n;//记录选的满足条件的最小的个数
	ans=inf;
    for(int i=1;i<=n;i++){//只选一个数的序列
        dp[1][i]=pre[i][0]+pre[i][n+1];
        if(dp[1][i]<=E){
            id=1;ans=std::min(ans,dp[1][i]);
        }
    }
    if(id==1){//没有比1小的选择了
        printf("%d %lld
",id,ans);return;
    }
    for(int i=2;i<=n;i++){//选i个数
        for(int j=i;j<=n;j++){//第i个数位j    
            dp[i][j]=inf;
            for(int k=i-1;k<j;k++){//上一个阶段的最后一个数位k
                int sum=-pre[k][n+1]+pre[k][j]+pre[j][n+1];
                dp[i][j]=std::min(dp[i][j],dp[i-1][k]+sum);
            }
            if(dp[i][j]<=E){//在误差范围之内
            	if(i>id) continue;//选的数比已选的大
                if(i<id){id=i;ans=dp[i][j];}//在保证id尽可能小的情况下再考虑值             
                if(i==id) ans=std::min(ans,dp[i][j]);
            }
        }
    }
    printf("%d %lld
",id,ans);
}
int main(){
    Init();
    Solve();
    return 0;
}
```