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的测量数目和使用那个测量数目能达到的最小误差.

Solution

“数据范围决定解题方法。” ——伟大的鲁迅先生

这道题的操作都带有绝对值(abs)，因此许多区间方法都无法使用，好在：

(1 <= N <= 100)

那么暴力求就是了。 题目大意：求出 k 个点，称之为观测集合，使得误差总和最小。误差分为三个部分：

最左的点往左产生的误差

最右的点往右产生的误差

观测集合最左最右两点间，即观测区间中每个非观测点产生的误差

对于观测集合中最左边的点往左的误差：

$设i为观测集合中最左的点，那么误差计算$ $L_i={\sum }_{j=1}^{i-1}2\ast |M_i-M_j|$

同理，对于最右边的点往右的点：

$R_i={\sum }_{j=1}^{i-1}2\ast |M_i-M_j|$

而中间的sum，则为相邻的两个观测点间所有点的误差和：

${\sum }_{i=l+1}^{r-1}|2\ast M_i-Sum(l,r)|$ //l r为相邻两个点的下标，l < r $其中Sum(l,r)：$ $Sum(l,r)=M_l+M_r$

也就是枚举(l,r)中每一个点，计算出这个区间的误差。

long long calc(int l,int r) { //枚举在(l,r) 中的每个点产生的误差得到和，返回结果 long long sum = M[l] + M[r]; long long ans = 0; for(int i = l+1;i<r;++i) ans += abs(2*M[i] - sum); return ans; }

当然可以预处理出来，但预处理也需要不少时间，想到n<=100的复杂度，直接暴力。 接下来可以处理前后误差的函数，比如pre(int i)计算i前面所有点产生的误差总和啊…… 这次就干脆用了预处理的写法(这个预处理似乎比较方便)

long long psum[110],ssum[110]; //计算误差前缀和 for(int i = 2;i<=n;++i) for(int j = 1;j<i;++j)//计算以i为左端点产生的前误差和 psum[i] += 2*abs(M[j] - M[i]); for(int i = 1;i<n;++i) for(int j = i+1;j<=n;++j)//计算以i为右端点产生的后误差和 ssum[i] += 2*abs(M[j] - M[i]);

然后我们发现了，对于现有的观测集合，如果在右边加入一个新的观测点，那么产生的观测变化只有：

$设i为之前的最右点，j为新的最右点$ $\Delta x=calc(i，j)-ssum[i]+ssum[j]$

于是我们得到了dp的状态转移方程：

$设k为选择k个观测点，i表示讨论范围在前i个点中$ $dp[k][i]=min\{dp[k-1][j]+calc(i,j)-ssum[j]+ssum[i]\}$ $j\in [k-1,i),i\in [k,n]$

特殊的，有：

$dp[1][i]=psum[i]+ssum[i]i\in [1,n]$ (((//终于用到了psum这个东西！

于是这道题就结束了，注意输出当前k中获得的最小解即可。 码风奇丑，还勿介意>_<：

#include <cstdio> #include <cstring> using namespace std; void read(long long &r) { static char c;r = 0; for(c=getchar();c>'9'||c<'0';c=getchar()); for(;c>='0'&&c<='9';r=(r<<1)+(r<<3)+c-48,c=getchar()); } inline long long abs(const long long &a) { return a>=0?a:-a; } inline long long min(const long long &a,const long long &b) { return a<b?a:b; } long long psum[110],ssum[110]; long long n,e; long long M[110]; long long dp[110][110]; const int INF = 1<<30; long long calc(const int &l,const int &r) { //枚举在(l,r) 中的每个点产生的误差得到和，返回结果 long long sum = M[l] + M[r]; long long ans = 0; for(int i = l+1;i<r;++i) ans += abs(2*M[i] - sum); return ans; } void getans() { int ans = 0; memset(dp,127,sizeof(dp)); //初始化k==1时的情况 long long minans = INF; for(int i = 1;i<=n;++i) { dp[1][i] = ssum[i] + psum[i]; minans = min(minans,dp[1][i]); } if(minans <= e) { printf("1 %lld",minans); return; } for(int k = 2;k<=n;++k) { if(ans) break;//找到答案，不用继续了 //选用k个结果时的情况 for(int i = k;i<=n;++i) { //枚举这个结果选哪一个，从k开始 //误差可以暴力计算 //也就是枚举上一个分界点 for(int j = k-1;j<=i;++j) { dp[k][i] = min(dp[k-1][j] + calc(j,i) - ssum[j] + ssum[i],dp[k][i]); if(dp[k][i] <= e) ans = k; } } } //枚举第k层得到最小答案 printf("%d ",ans); for(int i = 1;i<=n;++i) minans = min(dp[ans][i],minans); printf("%lld",minans); } void init() { //计算误差前缀和 for(int i = 2;i<=n;++i) for(int j = 1;j<i;++j)//计算以i为左端点产生的前误差和 psum[i] += 2*abs(M[j] - M[i]); for(int i = 1;i<n;++i) for(int j = i+1;j<=n;++j)//计算以i为右端点产生的后误差和 ssum[i] += 2*abs(M[j] - M[i]); } int main() { read(n); read(e); for(int i = 1;i<=n;++i) read(M[i]); init(); getans(); return 0; }