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

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^{i-1}_{j=1} 2 *|M_i - M_j|$

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

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

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

$sum^{r-1}_{i=l+1}{| 2 * 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;
}