C++(g++ 7.5.0) 解法, 执行用时: 1593ms, 内存消耗: 2724K, 提交时间: 2023-07-01 23:42:39

#include<bits/stdc++.h>
using namespace std;
const int N = 1E5 + 5;
int n;
long long a[N], w, f[N], sum[N];
int main()
{
    cin >> n >> w;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    for (int i = 1; i <= n; i++) {
        f[i] = 0x3F3F3F3F3F3F3F3F;
        long long minx = a[i], maxx = a[i];
        for (int j = i - 1; j >= 0; j--) {
            if (sum[i] - sum[j] <= w)
                f[i] = min(f[i], f[j] + sum[n] - sum[j] + maxx - minx);
            else break;
            minx = min(minx, a[j]);
            maxx = max(maxx, a[j]);
        }
    }
    cout << f[n];
}

C++11(clang++ 3.9) 解法, 执行用时: 1778ms, 内存消耗: 3168K, 提交时间: 2019-11-03 22:02:30

#include <bits/stdc++.h>
using namespace std;
int n,w;
long long f[100005],s[100005],a[100005];
long long maxx, minn;
int main() {
	cin>>n>>w;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	for(int i=1; i<=n; i++) {
		f[i]=f[i-1]-s[i-1];
		maxx=a[i];
		minn=a[i];
		for(int j=i-2; j>=0&&s[j]>=s[i]-w; j--) {
			maxx=max(maxx,a[j+1]);
			minn=min(minn,a[j+1]);
			if(f[i]>f[j]-s[j]+maxx-minn)
				f[i]=f[j]-s[j]+maxx-minn;
		}
		f[i]+=s[n];
	}
	cout<<f[n];
}