題目描述#
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 一個人把木筏從對岸划回來接下一批的奶牛的時間。
輸入輸出格式#
輸入格式：
* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Line i+1 contains a single integer: M_i
輸出格式：
* Line 1: The minimum time it takes for Farmer John to get all of the cows across the river.
輸入輸出範例#
輸入範例 #1：
5 10
3
4
6
100
1
輸出範例 #1：
50
說明#
There are five cows. Farmer John takes 10 minutes to cross the river alone, 13 with one cow, 17 with two cows, 23 with three, 123 with four, and 124 with all five.
Farmer John can first cross with three cows (23 minutes), then return (10 minutes), and then cross with the last two (17 minutes). 23+10+17 = 50 minutes total.
我的 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;
}