問題の説明#
農夫ジョンと彼の N (1 <= N <= 2,500) 頭の牛は、川を渡ることを計画していますが、彼らの渡河手段はただ 1 つの筏だけです。牛は船を漕ぐことができないため、渡河の間、ジョンは常に筏に乗っていなければなりません。その上で、筏に乗っている牛の数が 1 増えるごとに、ジョンはより多くの時間をかけて筏を対岸に漕がなければなりません。ジョンが一人で筏に乗って対岸に漕ぐのにかかる時間は M (1 <= M <= 1000) 分です。筏に乗っている牛の数が i-1 から i に増えると、ジョンは M_i (1 <= M_i <= 1000) 分だけ筏を漕ぐ必要があります（つまり、1 頭の牛が船に乗っている場合、ジョンは M+M_1 分かかります。2 頭の牛が船に乗っている場合、時間は M+M_1+M_2 分になります。以降も同様です）。では、ジョンがすべての牛を対岸に連れて行くために最低限どれくらいの時間がかかるでしょうか？もちろん、この時間にはジョンが一人で筏を対岸に漕いで次の牛を迎えに戻ってくる時間も含まれます。
入出力形式#
入力形式：
* 1 行目：2 つの整数 N と M がスペースで区切られています。
* 2 行目から N+1 行目：各行には 1 つの整数 M_i が含まれています。
出力形式：
* 1 行目：農夫ジョンがすべての牛を川を渡るのにかかる最小時間。
入出力例#
入力例 #1：
5 10
3
4
6
100
1
出力例 #1：
50
説明#
牛は 5 頭います。農夫ジョンは 1 人で川を渡るのに 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;
}