题目

类似二维费用背包。

$f_{i,j,k}$ 表示前 $i$ 个线段， $[0,j]$ 花费为 $k$ 的最大收益。

$f_{i,en{d}_i,k}=\max (f_{i-1,en{d}_i,k},f_{i-1,star{t}_i,k-c_i}+v_i)$。

省去第一维：

$f_{en{d}_i,k}=\max (f_{en{d}_i,k},f_{star{t}_i,k-c_i}+v_i)$。

而一般的背包在购买物品时，先买 $A$ 再买 $B$、先买 $B$ 再买 $A$，两者是等效的，而对于此题，要求是从 $0$ 开始的连续轨道，先造 $[0,2]$ 再造 $[2,3]$、先造 $[2,3]$ 再造 $[0,2]$ 是不等效的，会直接导致状态转移的缺失，我们应当将轨道先按右端点排序保证转移的有效性。

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct Seg{
	int x, w, f, c;
}a[10005];
bool cmp(Seg x, Seg y) {return (x.x + x.w) < (y.x + y.w);}
int L, n, B, f[2][1005][1005];
signed main()
{
	ios::sync_with_stdio(false);
	std::cin.tie(0);
	
	cin >> L >> n >> B;
	
	for(int i=1; i<=n; i++)
		cin >> a[i].x >> a[i].w >> a[i].f >> a[i].c;
	 
	memset(f, 0x80, sizeof(f));
	
	f[0][0] = 0;
	for(int i=1; i<=n; i++)
		for(int k=0; k + a[i].c <= B; k++)
			f[a[i].x + a[i].w][k + a[i].c] = max(f[a[i].x + a[i].w][k + a[i].c], f[a[i].x][k] + a[i].f);
		
	int ans = -1;
	for(int k=0; k<=B; k++)
		ans = max(ans, f[L][k]);
	cout << ans;
	return 0;
}