CF-1203F

题意

给两个序列 $a[],b$ ，你拥有的技能点为 $r(1\le r\le 3e4)$ ，只有当技能点 $\ge a_i$ 时，才可以做第 $i$ 份工作，技能点加上 $b_i$

1. 问他能否完成这 $n$ 份工作
2. 如果不能，最多能完成几份

题解

1. 显然，对于 $b_i\ge 0$ ，我们以 $a_i$ 排序；对于 $b_i< 0$ ，我们以 $a_i+b_i$ 排序。因为对于 $x,y$ 两个工作，假设 $xa+xb<ya+yb$ ，如果 $r+xb<ya$ ，那么一定有 $r+yb<ax$
2. 对于 $b_i\ge 0$ 容易求解；对于 $b_i< 0$ ，使用 $dp$ 来求解，同样以 $a_i+b_i$ 排序，$dp[i][j]$ 表示前 $i$ 份工作剩余 $j$ 技能点的最大完成数。

代码

int dp[N];
vector<pii>q,w;
bool cmp(pii x,pii y){
    retrun x.fi+x.se>y.fi+y.se;
}
int main() {
    int n,r,a,b;
    in(n,r);
    for0(i,n){
        in(a,b);
        if(b>=0){
            q.pu_b(pii(a,b));
        }else{
            w.pu_b(pii(a,b));
        }
    }
    sort(q.begin(),q.end());
    sort(w.begin(),w.end(),cmp);
    int ans=0;
    for(auto i:q){
        if(r>=i.fi){
            r+=i.se;
            ans++;
        }else{
            break;
        }
    }
    int maxx=0;
    for(auto i:w){
        for(int j=max(i.fi,-i.se);j<=r;j++){
            dp[j+i.se]=max(dp[j]+1,dp[j+i.se]);
            maxx=max(dp[j+i.se],maxx);
        }
    }
    out(ans+maxx,1);
    return 0;
}