題目描述#
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 一個人把木筏從對岸划回來接下一批的奶牛的時間。
輸入輸出格式#
輸入格式：
* 第 1 行：兩個以空格分隔的整數：N 和 M
* 第 2 行..N+1 行：第 i+1 行包含一個整數：M_i
輸出格式：
* 第 1 行：Farmer John 將所有奶牛過河所需的最短時間。
輸入輸出樣例#
輸入樣例 #1：
5 10
3
4
6
100
1
輸出樣例 #1：
50
說明#
有五頭奶牛。Farmer John 自己過河需要 10 分鐘，帶一頭奶牛過河需要 13 分鐘，帶兩頭奶牛過河需要 17 分鐘，帶三頭奶牛過河需要 23 分鐘，帶四頭奶牛過河需要 123 分鐘，帶五頭奶牛過河需要 124 分鐘。
Farmer John 可以先帶三頭奶牛過河（23 分鐘），然後返回（10 分鐘），然後帶最後兩頭奶牛過河（17 分鐘）。23+10+17 = 50 分鐘總共。
我的 WA 思路#
f[牛數][返回次數]=時間
初值為無限大
f[0][0]=m;
f[i][j]=min(f[i-1][j]+tz[i],f[i-1][j-1]+m+tz[1])
然後發現不應該+tz[i]，而當前是這條船的第幾頭牛又不知道
所以搞不定
AC 思路#
f[i]初始化為m[i]的前綴和+m
即為把所有牛裝到船上的解
然後遍歷每頭牛，檢查從任意位置斷開是否有更優解
#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=2505;
int tz[MAXN]={0};
int f[MAXN];
int n,m;
int main(){
cin>>n>>m;
f[0]=m;
for(int i=1;i<=n;++i){
cin>>tz[i];
f[i]=tz[i]+f[i-1];
}
for(int i=2;i<=n;++i){
for(int j=1;j<=i;++j){
f[i]=min(f[j]+f[i-j]+m,f[i]);
}
}
cout<<f[n]<<endl;
return 0;
}