记录编号	24678	评测结果	AAAAAAAAAA
题目名称	[USACO Jan09] 气象牛	最终得分	100
用户昵称	Pom	是否通过	通过
代码语言	C++	运行时间	0.272 s
提交时间	2011-04-14 17:38:21	内存使用	0.30 MiB

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

const int MAXN=107;
const int oo=1000000000;

int n,i,j,k,f[MAXN][MAXN],E,a[MAXN],anss=1000,ansc;

int qian(int x)
{
	int re=0;
	for (int i=1;i<x;i++)
		re+=2*abs(a[i]-a[x]);
	return re;
}

int hou(int x)
{
	int re=0;
	for (int i=x+1;i<=n;i++)
		re+=2*abs(a[i]-a[x]);
	return re;
}

int cal(int A,int B)
{
	int re=0;
	for (int i=A+1;i<=B-1;i++)
		re+=abs(2*a[i]-a[A]-a[B]);
	return re;
}

int main()
{
	freopen("baric.in","r",stdin);
	freopen("baric.out","w",stdout);
	scanf("%d%d",&n,&E);
	for (i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			f[i][j]=oo;
	for (i=1;i<=n;i++)
		for (j=1;j<=i;j++)
		{
			if (j==1) f[i][j]=qian(i)+hou(i);
			else
				for (k=j-1;k<i;k++)
					f[i][j]=min(f[i][j],f[k][j-1]+cal(k,i)-hou(k)+hou(i));
		}
	for (i=1;i<=n;i++)
		for (j=1;j<=i;j++)
			if (f[i][j]<=E)
				if (j<anss || j==anss && f[i][j]<ansc)
				{
					anss=j;
					ansc=f[i][j];
				}
	printf("%d %d\n",anss,ansc);
	return 0;
}