题解
先排序，把整个轨道考虑的顺序弄起来，再做01背包。
注意状态的可行性。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
using namespace std;
typedef long long ll;
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
int L,n,B,dp[1005][1005];
struct C{
int l,r,fun,cost;
bool operator <(C &a){
return l<a.l||(l==a.l&&r<a.r);
}
}comp[10005];
void init(){
L=read(),n=read(),B=read();
for(int i=1;i<=n;i++)
comp[i].l=read(),comp[i].r=read()+comp[i].l,
comp[i].fun=read(),comp[i].cost=read();
sort(comp+1,comp+1+n);
}
void solve(){
int c_,l_,r_,f_;
memset(dp,-1,sizeof(dp));
for(int i=0;i<=B;i++)dp[i][0]=0;
for(int i=1;i<=n;i++){
c_=comp[i].cost,l_=comp[i].l,r_=comp[i].r,f_=comp[i].fun;
for(int j=B;j>=c_;j--)
if(dp[j-c_][l_]>=0)
dp[j][r_]=max(dp[j][r_],dp[j-c_][l_]+f_);
}
printf("%d\n",dp[B][L]);
}
int main(){
init();
solve();
return 0;
}