题解 | #牛妹的招聘#

一.题目描述
NC516牛妹的招聘
每一个人都有一个聪明值Si(-1000<=Si<=1000)和勤奋值Fi(-1000<=Fi<=1000)。希望选入所有人的Si+Fi的总和最大，并且选中的所个人聪明值与勤奋值的和不能是负数，求出最大的总和。
图片说明
二.算法(单调栈)
对于n个人每个人存在两个状态就是选择或者不选择，如果我们暴力进行那么就之间 $2^{n}$ 的复杂度，很显然是会直接爆炸的。不如我们换一种思路利用单调栈去维护最大值，可以对时间进行极大的优化。开始的时候我们用一个q记录所有可能达到的聪明值的和和与勤奋值的和，如果利用单调栈维护最大值，进行提前淘汰，就会减少很多无用搜索。我们开始要按聪明值和对数组进行排序，如果聪明值的和相等，按勤奋值和排序。建立一个单调(vector实现)，对q进行遍历，由于是按聪明值的和从小到大排序，所以当前聪明值加和总是比单调栈栈顶的聪明值累加和大并且勤奋值也不小于栈顶的，那很显然单调栈栈顶组合肯定不会是最大总和，进行出栈。遍历完之后，再将q替换为单调栈(为了方便实现栈的实现利用的是vector)。下面是完整代码：

class Solution {
public:
    int smartSum(int number, vector<int>& si, vector<int>& fi) {
       vector<pair<int,int>>q;
        //新建一个数组存储可以实现的聪明值和勤奋值的和
        q.push_back({0,0});
        for(int i=0;i<number;i++){
            int num=q.size();
            for(int j=0;j<num;j++){
                //对可以实现的聪明值和勤奋值进行记录
                q.push_back({q[j].first+si[i],q[j].second+fi[i]});
            }
            //先比较聪明值后比较勤奋值
            sort(q.begin(),q.end());
            //利用vector来实现单调栈
            vector<pair<int,int>>st;
            for(int j=0;j<q.size();j++){
                //如果勤奋值和聪明值均比栈顶大 那么久跟新栈顶
                while(!st.empty()&&st.back().second<=q[j].second){
                    st.pop_back();
                }
                st.push_back(q[j]);
            }
            //将单调栈和数组进行交换
            swap(q,st);
            st.clear();
        }
        int ans=0;//返回最大的总和
        for(int i=0;i<q.size();i++){
            if(q[i].first>0&&q[i].second>0){
                ans=max(ans,q[i].first+q[i].second);
            }
        }
        return ans;
    }
};

时间复杂度：每次对于可以实现的聪明值和勤奋值都要记录并且排序所以复杂度是 $O(n^{2}logn)$
空间复杂度： $O(2*n)$ 需要额外开辟空间来存储勤奋值和聪明值
优缺点：感觉没什么优缺点，题目的难度比较大，思路和代码都不简单
三.算法(动态规划)
图片说明
对于每一个的选择是捆绑选择，也就是你选择该同学的聪明值就必须要接收其勤奋值，所以背包的想法久出现了，所以对于本题我们也可以使用动态规划的思想进行求解，我们可以将聪明值看作背包容量，勤奋值看作要装入背包物品的价值，是一个较为复杂的01背包问题dp[n]表示聪明值为n的情况可以获得dp[n]大小的勤奋值，每当我们使用了si[i]的聪明值可以获得fi[i]的勤奋值，所以状态转移方程才会是 $dp[j]=dp[j-si[i]]+fi[i]$ ，下面是完整代码：

class Solution {
public:
    int smartSum(int number, vector<int>& si, vector<int>& fi) {
        int mi=0;
        int mx=0; 
        int dp[100005];
        fill(dp,dp+100005,-1e9);
        //mi mx是对上下边界进行记录
        for(int i=0;i<number;i++){
            if(si[i]<0) {
                mi+=si[i];
            } else {
                mx+=si[i];
            }
        }
        int num=mx-mi; //背包的体积
        dp[-mi]=0;
        //由于体积存在正负 所以对不同体积进行分类讨论
        for(int i=0;i<number;i++){
            //体积是正数
            if(si[i]>0){
                //是正数就按照正常的背包进行状态转移
                for(int j=num;j>=si[i];j--)
                {
                    if(dp[j-si[i]]!=-1e9)
                    {
                        if(dp[j-si[i]]+fi[i]>dp[j]){
                            dp[j]=dp[j-si[i]]+fi[i];
                        }
                    }
                }
            } else {
                //体积是负数 就要从0到num加上si[i]这个范围进行动态规划
                for(int j=0;j<=num+si[i];j++) {
                    if(dp[j-si[i]]!=-1e9){
                        if(dp[j-si[i]]+fi[i]>dp[j]){
                            dp[j]=dp[j-si[i]]+fi[i];
                        }
                    }
                }
            }
        }
        int mxx=-1e9;//返回最大值
         //如果聪明值累加和大于0，同时勤奋值累加和大于0，取两者之和最大值
        for(int i=-mi+1;i<=num;i++){
            if(dp[i]>0){
                if(dp[i]+i+mi>mxx){
                    mxx=dp[i]+mi+i;
                }
            }
        }
        if(mxx==-1e9) return 0;
        return mxx;
    }
};

时间复杂度： $O(n^{2})$ 内外有双重循环，所以复杂度到 $n^{2}$ 的级别
空间复杂度： $O(n)$ 需要额外空间的dp数组来进行动态规划
优缺点：思路相对比较复杂，但是代码相比算法二简单，也便于实现