记录编号	153514	评测结果	AAAAAAAAAA
题目名称	[USACO Mar08] 奶牛渡河	最终得分	100
用户昵称	devil	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2015-03-17 21:54:29	内存使用	0.34 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN=2510;
const int MAX_INT=0x7fffffff;
const int MAXT=210;

int m[MAXN];
int sum[MAXN];
int f[MAXN];

int main()
{
    ///freopen("sample_data.in","r",stdin);
    freopen("cowriver.in","r",stdin);
    freopen("cowriver.out","w",stdout);
    int N,M;scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)
    {
        scanf("%d",&m[i]);
        sum[i]=sum[i-1]+m[i];
        f[i]=sum[i]+M;
    }
    for(int i=1;i<=N;i++)
    {
        ///f[i][1]=sum[i]+M;
        for(int k=1;k<i;k++)
            f[i]=min(f[i],f[k]+sum[i-k]+2*M);
    }
    printf("%d\n",f[N]);
    return 0;
}