记录编号	38330	评测结果	AWWWWWWWWW
题目名称	771.[USACO Open09] 放牧2	最终得分	10
用户昵称	QhelDIV	是否通过	未通过
代码语言	C++	运行时间	0.062 s
提交时间	2012-04-17 15:09:29	内存使用	15.54 MiB

#include <fstream>
#include <cstdlib>
using namespace std;
ifstream fin("graze2.in");
ofstream fout("graze2.out");
int N,S,remain,Map[2000],reflex[2000],f[2000][2000],Max=~0u>>1;
void Initialize()
{
int i,temp;
	fin>>N>>S;temp=(S-1)/(N-1)-1;
	for(i=1;i<=N;i++)
	{
		fin>>Map[i];
		reflex[i]=i*temp;
	}
	remain=S-temp*N;
}

void dp()
{
int i,j;	
	for(i=1;i<=N;i++)
	{
		Max=~0u>>1;
		for(j=0;j<=remain;j++)
		{
			f[i][j]=min(f[i-1][j],f[i-1][j-1])+abs(reflex[i]+j-Map[i]);
			Max=min(Max,f[i][j]);
		}
	}
	fout<<Max<<endl;
}

int main()
{
	Initialize();
	
	dp();
	
	fin.close();
	fout.close();
	return 0;
}