$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

1. 利用二分找出满足条件的最小长度
2. f[i]表示以 i 为右端点，选择第 i 个元素的最小代价
3. 中间相隔元素不超过 k 个的状态转移：f[i] = min{f[j]} + w[i] (i - k - 1 <= j <= i - 1)

可参考： 烽火传递

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 50010;

int n,m;
int w[N];
int f[N],q[N];

bool check(int k)
{
    f[0]=0;
    int hh=0,tt=0;
    for(int i=1;i<=n;i++)
    {
        if(q[hh]<i-k-1) hh++; 
        f[i]=f[q[hh]]+w[i]; //f[i] = min{f[j]} + w[i] (i - k - 1 <= j <= i - 1)
        while(hh<=tt&&f[q[tt]]>=f[i]) tt--; //严格单调递增，队头即最小值
        q[++tt]=i;
    }

    for(int i=n-k;i<=n;i++)
        if(f[i]<=m)
            return true;
    return false;
}

int main()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++) cin>>w[i];

    //二分判断该长度所带来的最少时间是否满足条件
    int l=0,r=n;
    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }

    cout<<r<<endl;

    return 0;
}