【动态规划】【记忆化搜索】【前缀和】信奥队过河

题目描述
叶老师带着他的N(1 <= N <= 2,500)个学生去参加省赛，他们要过一条河，但他们所有的渡河工具，仅仅是一个木筏。
由于学生不会划船，在整个渡河过程中，叶老师必须始终在木筏上。在这个基础上，木筏上的学生数目每增加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行: 第i+1为1个整数：M_i
输出
第1行: 输出1个整数，为叶老师把所有学生都载过河所需的最少时间
样例输入

5 10
3
4
6
100
1

样例输出

50

提示
【输入说明】
叶老师带了5个学生出门。如果是单独把木筏划过河，叶老师需要花10分钟，带上1个学生的话，是13分钟，2个学生是17分钟，3个学生是23分钟，4个学生是123分钟，将5个学生一次性载过去，花费的时间是124分钟。
【输出说明】
叶老师第一次带3个学生过河（23分钟），然后一个人划回来（10分钟），最后带剩下的2个学生一起过河（17分钟），总共花费的时间是23+10+17 = 50分钟。

动态规划做法

#pragma GCC optimize(2)
#include
#define abss(x) ((x)>(0)?(x):(-1)*(x))
#define maxs(a,b) ((a)>(b)?(a):(b))
#define mins(a,b) ((a)<(b)?(a):(b))
#define FOR(i,a,b) for(register int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(register int i=(a);i>=(b);i--)
#define mem(a) memset(a,0,sizeof(a))
const int INF (1<<30);
const int inf (-1<<30);
using namespace std;

int dp[3000],presum[3000];

int main(){
    int n,m;
    cin>>n>>m;
    int x;
    FOR(i,1,n){
        cin>>x;
        presum[i]=presum[i-1]+x;
    }
    FOR(i,1,n){
        int min0=INF;
        FOR(j,1,i)
            min0=min(min0,dp[i-j]+presum[j]+2*m);
        dp[i]=min0;
    }
    cout< 
记忆化搜索做法
 
#pragma GCC optimize(2)
#include
#define abss(x) ((x)>(0)?(x):(-1)*(x))
#define maxs(a,b) ((a)>(b)?(a):(b))
#define mins(a,b) ((a)<(b)?(a):(b))
#define FOR(i,a,b) for(register int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(register int i=(a);i>=(b);i--)
#define mem(a) memset(a,0,sizeof(a))
const int INF (1<<30);
const int inf (-1<<30);
using namespace std;

int presum[3000],data[3000];

int search(int x,int m){
	if(x==0) return 0;
	if(data[x]!=0) return data[x];
	int res=INF;
	FOR(i,1,x){
		res=min(res,search(x-i,m)+presum[i]+2*m);
	}
	return data[x]=res;
}

int main(){
	int n,m;
    cin>>n>>m;
    int x;
    FOR(i,1,n){
        cin>>x;
        presum[i]=presum[i-1]+x;
    }
    cout<