贪心+DP。
对于一个点，后选显然比先选好，也就是说每个点都对应了唯一一个来源。
于是我们可以把每个点所能回溯到的点的收益值从大到小排序，贪心地选前缀。
定义 \(f_{i,j}\) 表示考虑了前 \(i\) 个点，剩下 \(j\) 个人，最大收益。
转移方程和 \(01\) 背包的一样。
\[f_{i,j}=f_{i-1,j-b_i} \]\[f_{i,j}=\max\limits_{t}(f_{i-1,j+t-b_i}+\sum\limits_{k=1}^{t}c_{vec_{i,k}}) \]注意边界,我因为 RE 调了半天....
复杂度 \(O(n^2)\)。代码很短。
code:
#include<bits/stdc++.h>
using namespace std;
const int N=5000+5,inf=INT_MAX>>1;
int n,m,k,a[N],b[N],c[N],l[N],f[N][N];
vector<int>vec[N];
bool cmp(int x,int y){return c[x]>c[y];}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m>>k;
for(int i=1;i<=n;++i){
cin>>a[i]>>b[i]>>c[i];
l[i]=i;
}
for(int i=1;i<=m;++i){
int u,v;cin>>u>>v;
l[v]=max(l[v],u);
}
for(int i=1;i<=n;++i)vec[l[i]].push_back(i);
for(int i=1;i<=n;++i)sort(vec[i].begin(),vec[i].end(),cmp);
memset(f,~0x3f,sizeof(f));f[0][k]=0;
for(int i=1;i<=n;++i){
for(int j=0;j<=5000;++j){
int v=0,w=0;
if(j-b[i]>=a[i])f[i][j]=f[i-1][j-b[i]];
for(int t=0;t<vec[i].size();++t){
++v;w+=c[vec[i][t]];
int p=j+v-b[i];
if(p>=a[i]&&p<=5000)f[i][j]=max(f[i][j],f[i-1][p]+w);
}
}
}
int ans=-1;
for(int j=0;j<=5000;++j)ans=max(ans,f[n][j]);
cout<<ans<<endl;
return 0;
}