记录编号	115008	评测结果	AAAAAAAAAA
题目名称	[USACO Jan09] 气象牛	最终得分	100
用户昵称	JSX	是否通过	通过
代码语言	C++	运行时间	0.060 s
提交时间	2014-08-12 20:04:49	内存使用	0.34 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 110
using namespace std;
int N,E;
int M[MAXN]={0};
int f[MAXN][MAXN]={0};

inline int ABS(int x){
	if(x>=0)	return x;
	else	return -x;
}

int MIN(int x,int y){
	if(x<y) return x;
	return y;
}

int F1(int k){//如果i小于s1,误差是:2*|Mi–M(s1)|
	int Ans=0;
	for(int m=1;m<=k-1;++m)
	{
		Ans+=( 2*ABS(M[m]-M[k]) );
	}
	return Ans;
}

int F2(int i){//如果i大于sK,误差为: 2*|Mi–M(sK)| 
	int Ans=0;
	for(int m=i+1;m<=N;++m)
	{
		Ans+=( 2*ABS((M[m]-M[i])) );
	}
	return Ans;
}

int F3(int k,int i){ //如果i在sj和s(j+1)之间,误差是: |2*Mi–Sum(sj,s(j+1))| 
	int Ans=0;
	for(int m=k+1;m<=i-1;++m)
	{
		Ans+=ABS(2*M[m]-(M[k]+M[i]));
	}
	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]=F2(i)+F1(i);
	
	for(int i=2;i<=N;++i)
	{
		for(int j=2;j<=i;++j)
		{
			int t=0x7fffffff;
			for(int k=j-1;k<=i;++k)
			{
				int temp=f[k][j-1]-F2(k)+F2(i)+F3(k,i);
				t=MIN(t,temp);
			}
			f[i][j]=t;
		}
	}

	bool flag=false;
	int t=0x7fffffff,z=0;
	for(int j=1;j<=N;++j)
	{
		for(int i=j;i<=N;++i)
		{
			if(f[i][j]<E){
				flag=true;
				z=j;
				if(flag){
					if(t>f[i][j])	t=f[i][j];
				}
			}
		}
		if(flag) {
			printf("%d %d",z,t);
			break;
		}		
	}
	
	return 0;
}