记录编号	169767	评测结果	AAAAAAAAAA
题目名称	[USACO Jan09] 气象牛	最终得分	100
用户昵称	lenibomb	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2015-07-10 15:19:55	内存使用	0.37 MiB

#include<cstdio>
#include<cstring>
using namespace std;
int n,e,m[105],f[105][105],sum[105],he[105][105];
int min(int a,int b)
{
	return a<b?a:b;
}
int to(int x)
{
	if(x<0)
	return -x;
	return x;
}
int Sum(int x,int y,int k)
{
	int aa;
	int ans=0;
	if(k==1)
	{
        for(int i=y+1;i<=n;i++)
		ans+=to(m[i]-m[y])*2;
	}
	if(k==2)
	{
		for(int i=x+1;i<=y-1;i++)
		{
			ans+=to(2*m[i]-m[x]-m[y]);
		}
	}
//	printf("%d ",ans);
	return ans;
}
int main()
{
	freopen("baric.in","r",stdin);
	freopen("baric.out","w",stdout);
	scanf("%d%d",&n,&e);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&m[i]);
	}
	for(int i=1;i<=n;i++)
	{
		f[i][1]=0;
		for(int j=1;j<=n;j++)  //预处理！
		{
			if(j==i) continue;
			 f[i][1]=2*to((m[j]-m[i]))+f[i][1];
		}
		sum[i]=Sum(i,i,1);
		for(int j=1;j<=n;j++)
		{
			he[i][j]=Sum(i,j,2);
		}
	}

/*	for(int i=1;i<=n;i++)
	{
		printf("%d   %d    \n",i,f[i][1]);
	}*/
/*	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		printf("XX ");
		for(int j=i+1;j<=n+1;j++)
		{
			sum[i][j]=m[i]+m[j];
			printf("%2d ",sum[i][j]);
		}
		printf("\n");
	}
*/
	for(int i=2;i<=n;i++)
	{
		for(int j=2;j<=i;j++)
		{
			f[i][j]=0x7ffffff;   //预处理最大道【i】，否则后续会爆，  吃"亏 "了
			for(int k=j-1;k<=i;k++)
			{
				//printf("%d  %d  %d  : %d  ",i,j,k,f[k][j-1]);
				f[i][j]=min(f[i][j],f[k][j-1]+he[k][i]+sum[i]-sum[k]);
				//printf(" %d  \n",f[i][j]);
				//printf("%d   %d  \n",f[k][j-1],Sum(k,i));
			}
		}
	}
	int kk=1000000;
	int zhi;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
		//	printf("%d ",f[i][j]);
			if(f[i][j]<=e)
			{
				if(j<kk)
				{
					kk=j;
					zhi=f[i][j];
				}
				if(j==kk)
				{
					zhi=min(zhi,f[i][j]);
				}
			}
		}
	}
	printf("%d %d",kk,zhi);
//	while(1);

}