记录编号	454965	评测结果	AAAAAAAAAA
题目名称	[USACO Jan09] 气象牛	最终得分	100
用户昵称	路人甲	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2017-09-30 17:45:38	内存使用	0.38 MiB

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int N=110;
int m[N],w[N][N],f[N][N],n,e;

int main() {
	freopen("baric.in","r",stdin);
	freopen("baric.out","w",stdout);
	memset(f,0x3f3f3f3f,sizeof f);
	memset(w,0,sizeof w);
	scanf("%d%d",&n,&e);
	for (int i=1; i<=n; ++i) scanf("%d",&m[i]);
	for (int i=0; i<=n; ++i) {
		for (int j=i+1; j<=n+1; ++j) {
			for (int k=i+1; k<j; ++k) {
				if (i==0) {
					w[i][j]+=2*abs(m[j]-m[k]);
					continue;
				}
				if (j==n+1) {
					w[i][j]+=2*abs(m[i]-m[k]);
					continue;
				}
				w[i][j]+=abs(2*m[k]-m[i]-m[j]);
			}
		}
	}
	f[0][1]=0;
	w[0][n+1]=1e9;
	for (int i=1; i<=n+1; ++i) {
		for (int j=1; j<=i+1; ++j) {
			for (int k=0; k<i; ++k) {
				if (j-1<=k+1){
					f[i][j]=min(f[i][j],f[k][j-1]+w[k][i]);
				}
			}
		}
	}
	for (int i=1;i<=n+2;++i){
		if (f[n+1][i]<=e){
			printf("%d %d\n",i-2,f[n+1][i]);
			return 0;
		}
	}
	return 0;
}