牛妹的招聘 题解

应该说是很难的一个题了
首先，要想到这种求最大值的应该转化成01背包，si作为容量，fi作为价值。
然后，要解决容量为负值的问题，那就再加一个数组用来存储加进去了多少个原本是负值的si
最后，在求最终答案的时候，记得把为了成为正数多加的减掉

class Solution {
public:
    /**
     *
     * @param number int整型 参加校招的同学人数
     * @param si int整型一维数组 这个同学的聪明值
     * @param siLen int si数组长度
     * @param fi int整型一维数组 这个同学的勤奋值
     * @param fiLen int fi数组长度
     * @return int整型
     */
    int smartSum(int number, int* si, int siLen, int* fi, int fiLen) {
        // write code here
        int sum = 0;
        int dp[100000],cnt[100000];
        int ans;
        for (int i = 0; i < number; i ++) {
            if(si[i]<0&&fi[i]<0)
            {
                si[i] = 0;fi[i]= 0;
                continue;
            }
            si[i]+=1000;
            sum+=si[i];
        }
        for(int i=sum+100;i>=0;--i)
            dp[i]=-0x3f3f3f3f,cnt[i]=0;
        dp[0]=0;
        for(int i=0;i<number;++i)
        {
            for(int j=sum;j>=si[i];--j)
            {
                if(dp[j-si[i]]+fi[i]-(cnt[j-si[i]]+1)*1000>dp[j]-(cnt[j])*1000)
                {
                    dp[j]=dp[j-si[i]]+fi[i];
                    cnt[j]=cnt[j-si[i]]+1;
                   // cout<<cnt[j]<<endl;
                }
            }
        }
        ans=0;
        for(int i=sum;i>=0;--i)
            if(i-(cnt[i])*1000>0&&dp[i]>0)
                ans=max(ans,dp[i]+i-(cnt[i])*1000);
        return ans;
    }
};

时间复杂度和空间复杂度就是01背包的
貌似解法也就这么一个。。