题目描述#
ファーマー・ジョンと彼の 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: 二つのスペースで区切られた整数: N と M
* Lines 2..N+1: Line i+1 には単一の整数: M_i が含まれます
出力フォーマット：
* Line 1: ファーマー・ジョンがすべての牛を川を渡らせるのにかかる最小時間。
输入输出样例#
入力サンプル #1：
5 10
3
4
6
100
1
出力サンプル #1：
50
说明#
牛は 5 頭います。ファーマー・ジョンは一人で川を渡るのに 10 分かかり、1 頭の牛と一緒だと 13 分、2 頭の牛と一緒だと 17 分、3 頭の牛と一緒だと 23 分、4 頭の牛と一緒だと 123 分、そして 5 頭全てだと 124 分かかります。
ファーマー・ジョンはまず 3 頭の牛と一緒に渡ります（23 分）、次に戻ります（10 分）、そして最後の 2 頭と一緒に渡ります（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;
}