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

#include<fstream>
#include<cmath>
#include<cstdlib>
#include<string>

using namespace std;

long f[101][101],a[1000001],n,m;

int main()
{
	long i,j,k,mn,tmp;
	ifstream fin("baric.in");
	ofstream fout("baric.out");
	fin>>n>>m;
	for(i=1;i<=n;i++)
		fin>>a[i];
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			f[i][j]=0x7fffffff;
	for(i=1;i<=n;i++)
	{
		f[i][1]=0;
		for(k=1;k<i;k++)
			f[i][1]+=2*abs(a[i]-a[k]);
		for(k=1;k<i;k++)
		{
			tmp=0;
			for(j=k+1;j<i;j++)
				tmp+=abs(2*a[j]-a[k]-a[i]);
			for(j=2;j<=k+1;j++)
				f[i][j]=min(f[i][j],f[k][j-1]+tmp);
		}
	}
	for(j=1;j<=n;j++)
	{
		mn=0x7fffffff;
		for(i=j;i<=n;i++)
		{
			tmp=0;
			for(k=i+1;k<=n;k++)
				tmp+=2*abs(a[k]-a[i]);
			mn=min(mn,f[i][j]+tmp);
		}
		if(mn<=m)
		{
			fout<<j<<' '<<mn<<endl;
			fin.close();
			fout.close();
			return 0;
		}
	}
	fin.close();
	fout.close();
	return 0;
}