记录编号	245890	评测结果	AAAAAAAAAA
题目名称	[USACO Mar08] 奶牛渡河	最终得分	100
用户昵称	YGOI_真神名曰驴蛋蛋	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2016-04-04 15:47:24	内存使用	0.31 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>   
using namespace std;
int w[2510];
int f[2510];
char c;
inline void read(int &k){k=0;
	do{c=getchar();}while(c<'0'||c>'9');
	do{k=k*10+c-'0';c=getchar();}while(c>='0'&&c<='9');
}
inline int mmin(const int &a,const int &b){return a>b?b:a;}
int main(){
	freopen("cowriver.in","r",stdin);
	freopen("cowriver.out","w",stdout);
	int n,x;
	read(n);read(x);w[0]=x+x;
	memset(f,63,n*4+16);f[0]=0;
	for(int i=1;i<=n;++i){read(x);w[i]=w[i-1]+x;}
	for(int i=1;i<=n;++i){
		for(int j=i;j<=n;++j){
			f[j]=min(f[j],f[j-i]+w[i]);
		}
	}
	printf("%d",f[n]-w[0]/2);
    return 0;
}