[動態規劃]USACO ：奶牛渡河 cowriver 解題報告

【題目描述】
Farmer John以及他的N(1 <= N <= 2,500)頭奶牛打算過一條河，但他們所有的渡河工具，僅僅是一個木筏。

由於奶牛不會划船，在整個渡河過程中，FJ必須始終在木筏上。在這個基礎上，木筏上的奶牛數目每增加1，FJ把木筏劃到對岸就得花更多的時間。

當FJ一個人坐在木筏上，他把木筏劃到對岸需要M(1 <= M <= 1000)分鐘。當木筏搭載的奶牛數目從i-1增加到i時，FJ得多花M_i(1 <= M_i <= 1000)分鐘才能把木筏劃過河（也就是說，船上有1頭奶牛時，FJ得花M+M_1分鐘渡河；船上有2頭奶牛時，時間就變成M+M_1+M_2分鐘。後面 的依此類推）。那麼，FJ最少要花多少時間，才能把所有奶牛帶到對岸呢？當然，這個時間得包括FJ一個人把木筏從對岸劃回來接下一批的奶牛的時間。

程序名: cowriver

輸入格式:

第1行: 2個用空格隔開的整數：N 和 M

第2..N+1行: 第i+1爲1個整數：M_i

輸入樣例 (cowriver.in):

5 10

3

4

6

100

1

輸入說明:

FJ帶了5頭奶牛出門。如果是單獨把木筏劃過河，FJ需要花10分鐘，帶上1頭奶牛的話，是13分鐘，2頭奶牛是17分鐘，3頭是23分鐘，4頭是123分鐘，將5頭一次性載過去，花費的時間是124分鐘。

輸出格式:

第1行: 輸出1個整數，爲FJ把所有奶牛都載過河所需的最少時間

輸出樣例 (cowriver.out):

50

輸出說明:

Farmer John第一次帶3頭奶牛過河（23分鐘），然後一個人劃回來（10分鐘），最後帶剩下的2頭奶牛一起過河（17分鐘），總共花費的時間是23+10+17 = 50分鐘。

【分析】

線性動態規劃。
狀態設定：F[i] 前i個奶牛渡河的最短時間

狀態轉移方程：F[i]=Min(F[i],F[j]+M+F[i-j]); (1<=j<=i)

目標結果：F[N]
 
【我的代碼】
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

int sum[2501];
int F[2501];
int N,M;

void init()
{
    scanf("%d %d\n",&N,&M);

    sum[0]=M;
    for (int i=1;i<=N;i++)
    {
        scanf("%d\n",&sum[i]);
        sum[i]+=sum[i-1];
    }
   
    return;
}

int Min(int a,int b)
{
    if(b<a)
        a=b;
    return a;
}
 
void dp()
{
    for (int i=1;i<=N;i++)
    {
        F[i]=sum[i];
        for (int j=1;j<=i;j++)
        {
            F[i]=Min(F[i],F[j]+M+F[i-j]);
        }
    }
    printf("%d\n",F[N]);
}

int main()
{
    freopen("cowriver.in","r",stdin);
    freopen("cowriver.out","w",stdout);
    init();
    dp();
    return 0;
}