原题链接

题解

1.当没有花费限制的时候，我们可以将其抽象为简单的背包问题
2.如果有了花费限制，那么我们就再加一维条件

3.如果一个线段能用，那么它前面一定是铺满的，那我们令线段按起点排序，通过某种运算，保证放这个线段时，前面的线段组成是最优的
比如在 \(i\) 点结尾位置花费 \(j\) 所达到的最优值，这个最优值与后面线段怎么摆无关，所以可以存起来减少重复运算，这也是dp的核心

code

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int start,len,v,c;
}seg[10005];
bool cmp(node a,node b)
{
    if(a.start!=b.start) return a.start<b.start;
    return a.len<b.len;
}

int f[1005][1005]={0};
int main()
{
    int l,n,b;
    cin>>l>>n>>b;
    for(int i=1;i<=n;i++)
    {
        cin>>seg[i].start>>seg[i].len>>seg[i].v>>seg[i].c;
    }

    sort(seg+1,seg+1+n,cmp);

    for(int i=0;i<=l;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int start=seg[j].start;
            if(start==i)
            {
                int ends=start+seg[j].len;
                if(i==0) f[ends][seg[j].c]=max(seg[j].v,f[ends][seg[j].c]);
                for(int k=seg[j].c;k<=b;k++) if(f[start][k-seg[j].c]) f[ends][k]=max(f[start][k-seg[j].c]+seg[j].v,f[ends][k]);
            }
        }
    }

    int ans=0;
    for(int i=1;i<=b;i++) ans=max(ans,f[l][i]);
    cout<<(ans?ans:-1);
    return 0;
}