首先对于 $b>0$ 的工作显然有个贪心，把 $b>0$ 的按 $a$ 从小到大排序
把能做的都做了，然后得到一个最大等级
剩下就是考虑 $b<0$ 的工作了，看到数据显然可以 $O(nr)$ 考虑 $dp$，设 $f[i][j]$ 表示考虑完前 $i$ 个工作，当前等级为 $j$ 时能完成的最大工作数
然后发现这样搞有点问题，因为工作考虑的顺序是会影响到最终答案的，可能先做后面的工作再来做前面的工作可以做两个，但是如果先做前面的再做后面的可能会发现等级不够了...
考虑给所有工作确定一个顺序，使得如果先做 $2$ 不能做 $1$ ，并且先做 $1$ 可以做 $2$ ，则把 $1$ 排在 $2$ 前面考虑
设 $x+b_2<a_1$，$x+b1>=a2$ （注意这里 $b<0$），那么有 $x<a_1-b_2,x>=a_2-b_1$，即 $a_2-b_1<a_1-b_2$
所以排序时根据 $a_1-b_2$ 从大到小排序即可
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<vector> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=107,M=60007; int n,m; struct dat { int a,b; dat (int _a=0,int _b=0) { a=_a,b=_b; } inline bool operator < (const dat &tmp) const { return a-tmp.b>tmp.a-b; } }; vector <dat> C,D; inline bool cmp(const dat &A,const dat &B) { return A.a<B.a; } int ans,f[N][M]; int main() { n=read(),m=read(); int a,b; for(int i=1;i<=n;i++) { a=read(),b=read(); if(b<0) D.push_back(dat(a,b)); else C.push_back(dat(a,b)); } sort(C.begin(),C.end(),cmp); sort(D.begin(),D.end()); for(auto A: C) if(m>=A.a) m+=A.b,ans++; memset(f,~0x3f,sizeof(f)); f[0][m]=0; int len=D.size(),res=0; for(int i=1;i<=len;i++) { for(int j=0;j<=m;j++) { f[i][j]=f[i-1][j]; if(j-D[i-1].b>=D[i-1].a) f[i][j]=max(f[i][j],f[i-1][j-D[i-1].b]+1); res=max(res,f[i][j]); } } printf("%d ",ans+res); return 0; }