初看是個數學問題，像是線性規劃求最優值的問題。其實還是動態規劃問題。

首先要算出一次載不同數量的牛過河需要的時間，就是數據給出的序列求前n項的和。設F[i]爲帶i頭牛過河並空載回來所需要的最少時間。最後結果就是F[N]-空載的時間。

狀態

* F[i] 帶i頭牛過河並空載回來所需要的最少時間
* G[i] 一次帶i頭牛過河所需要的時間 

狀態轉移方程

* F[i]=min{ F[k] + G[i-k] } (0<=k<=i-1) 

邊界條件

* F[1]=G[1]+G[0]; 

目標結果 F[N]-G[0]

/*
ID: cmykrgb1
PROG: river
LANG: C++
*/

#include <iostream>
#define MAX 2501
using namespace std;

int N,Ans;
int M,F[MAX],G[MAX];

void init()
{
    int i;
    freopen("river.in","r",stdin);
    freopen("river.out","w",stdout);
    cin >> N >> G[0];
    for (i=1;i<=N;i++)
    {
        cin >> M;
        G[i]=G[i-1]+M;
    }
}

void dynamic()
{
    int i,k,min;
    F[1]=G[1]+G[0];
    for (i=2;i<=N;i++)
    {
        min=0x7FFFFFFF;
        for (k=0;k<=i-1;k++)
        {
            if (F[k]+G[i-k]+G[0]<min)
                min=F[k]+G[i-k]+G[0];
        }
        F[i]=min;
    }
    Ans=F[N]-G[0];
}

int main()
{
    init();
    dynamic();
    cout << Ans << endl;
    return 0;
}