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为观测集合中最左的点，那么误差计算设i为观测集合中最左的点，那么误差计算设i为观测集合中最左的点，那么误差计算

Li=∑j=1i−12∗∣Mi−Mj∣L_i = \sum^{i-1}_{j=1} 2 *|M_i - M_j|Li=∑j=1i−12∗∣Mi−Mj∣

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

Ri=∑j=1i−12∗∣Mi−Mj∣R_i = \sum^{i-1}_{j=1} 2 *|M_i - M_j|Ri=∑j=1i−12∗∣Mi−Mj∣

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

∑i=l+1r−1∣2∗Mi−Sum(l,r)∣\sum^{r-1}_{i=l+1}{| 2 * M_i - Sum(l, r) | }∑i=l+1r−1∣2∗Mi−Sum(l,r)∣ //l r为相邻两个点的下标，l < r

其中Sum(l,r)：其中Sum(l,r)：其中Sum(l,r)：

Sum(l,r)=Ml+MrSum(l,r) = M_l + M_rSum(l,r)=Ml+Mr

也就是枚举(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为新的最右点设 i为之前的最右点，j为新的最右点设i为之前的最右点，j为新的最右点

Δx=calc(i，j)−ssum[i]+ssum[j]\Delta x = calc(i，j) - ssum[i] + ssum[j]Δx=calc(i，j)−ssum[i]+ssum[j]

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

设k为选择k个观测点，i表示讨论范围在前i个点中设k为选择k个观测点，i表示讨论范围在前i个点中设k为选择k个观测点，i表示讨论范围在前i个点中

dp[k][i]=min{dp[k−1][j]+calc(i,j)−ssum[j]+ssum[i]}dp[k][i] = min\{dp[k-1][j] + calc(i,j) - ssum[j] + ssum[i]\}dp[k][i]=min{dp[k−1][j]+calc(i,j)−ssum[j]+ssum[i]}

j∈[k−1,i),i∈[k,n]j \in [k-1,i), i \in [k,n]j∈[k−1,i),i∈[k,n]

特殊的，有：

dp[1][i]=psum[i]+ssum[i]i∈[1,n]dp[1][i] = psum[i] + ssum[i] i \in [1,n]dp[1][i]=psum[i]+ssum[i]i∈[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;

}

巴特西

[JZOJ]1293.气象牛[区间DP]