Luogu P2904 River Crossing

Problem Description#

Farmer John and his N (1 <= N <= 2,500) cows plan to cross a river, but all they have is a raft. Since the cows cannot row, FJ must always stay on the raft throughout the entire crossing. In addition, as the number of cows on the raft increases by 1, FJ takes more time to row the raft to the other side. When FJ is alone on the raft, it takes him M (1 <= M <= 1000) minutes to row it to the other side. When the number of cows on the raft increases from i-1 to i, FJ takes an additional M_i (1 <= M_i <= 1000) minutes to row the raft across the river (i.e., when there is 1 cow on the raft, FJ takes M+M_1 minutes to cross the river; when there are 2 cows on the raft, the time becomes M+M_1+M_2 minutes, and so on). So, what is the minimum time that FJ needs to bring all the cows to the other side? Of course, this time includes the time for FJ to row the raft back to the other side to pick up the next batch of cows.

Input/Output Format#

Input Format:

Line 1: Two space-separated integers: N and M
Lines 2..N+1: Line i+1 contains a single integer: M_i

Output Format:

Line 1: The minimum time it takes for Farmer John to get all of the cows across the river.

Input/Output Example#

Input Example #1:

Output Example #1:

Explanation#

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.

My WA Approach#

f[cow_count][return_count]=time
Initialize to infinity
f[0][0]=m;
f[i][j]=min(f[i-1][j]+tz[i],f[i-1][j-1]+m+tz[1])
Then I realized that I shouldn't +tz[i], and I don't know which cow is the current one on the boat
So I couldn't solve it

AC Approach#

Initialize f[i] to the prefix sum of m[i] + m
This is the solution when all cows are on the boat
Then iterate through each cow and check if there is a better solution by splitting at any position

#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;
}