C++(g++ 7.5.0) 解法, 执行用时: 504ms, 内存消耗: 2724K, 提交时间: 2023-01-03 15:25:55

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int a[N], maxx[N], anss[N];
signed main()
{
    int i, j, k, n, m, sum;
    scanf("%lld %lld", &n, &m);
    for (i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
        if (a[i] > m)
            return puts("-1"), 0;
        anss[i] = anss[i - 1] + a[i];
        sum = maxx[i] = a[i];
        for (j = i - 1; j >= 1; j--)
        {
            sum += a[j];
            if (sum > m)
                break;
            k = max(maxx[i], a[j]);
            if (anss[i] > anss[j - 1] + k)
            {
                anss[i] = anss[j - 1] + k;
            }
            maxx[i] = k;
        }
    }
    cout << anss[n] << endl;
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 20ms, 内存消耗: 1888K, 提交时间: 2020-04-12 17:11:24

#include<bits/stdc++.h>
using namespace std;
int a[100010],q[100010],dp[100010];
int main()
{
	int n;
	long long m;
	cin>>n>>m;
	bool flag=true;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]>m)
			flag=false;
	}
	if(!flag)
	{
		puts("-1");
		return 0;
	}
	int head=0,tail=0;
	long long sum=0;
	for(int i=1,j=0;i<=n;i++)
	{
		sum=sum+a[i];
		while(sum>m)
		{
			j++;
			sum=sum-a[j];
		}
		while(head<=tail&&q[head]<j)
			head++;
		while(head<=tail&&a[q[tail]]<=a[i])
			tail--;
		q[++tail]=i;
		dp[i]=dp[j]+a[q[head]];
		for(int k=head;k<=tail;k++)
			dp[i]=min(dp[i],dp[q[k]]+a[q[k+1]]);
	}
	cout<<dp[n]<<endl;
	return 0;
}

C++ 解法, 执行用时: 394ms, 内存消耗: 1556K, 提交时间: 2022-07-06 19:52:55

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,w[N],f[N],hh,tt,sum[N];
int main()
{
	memset(f,0x3f,sizeof f);
	f[0]=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&w[i]),sum[i]=sum[i-1]+w[i];
	for(int i=1;i<=n;i++)
	{
		int maxx=w[i];
		for(int j=i-1;sum[i]-sum[j]<=m && j>=0;j--)
		{
			f[i]=min(f[i],f[j]+maxx);
			maxx=max(maxx,w[j]);
		}
	}
	printf("%d",f[n]);
	return 0;
}