This post is written in Chinese. Please consider using Google Translate

初看是个数学问题，像是线性规划求最优值的问题。其实还是动态规划问题。

首先要算出一次载不同数量的牛过河需要的时间，就是数据给出的序列求前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;
}