生产口罩题解_牛客博客

做法1：AC
考虑动态规划， $dp[i][j]$ 代表选了 $1-i$ 的工厂后，用 $j$ 个人所能生产的最多的口罩个数。那么 $dp$ 转移方程式就很简单了,假设我们现在枚举到了第i个人的第 $h$ 种策略，其中 $a_{ih}$ 代表人数， $b_{ih}$ 代表生产的口罩数。 $dp[i][j+a_{ih}]=max(dp[i][j+a_{ih}],dp[i-1][j]+y_{ih})$ ，需要注意的是第i个生产线也可以选择不选任何策略。其实我们也可以用滚动维数组来进行动态规划，只不过这里为了方便大家理解，说明的时候就是用的二维的，代码一维二维都有。所以这题我们就做完了，时间复杂度 $O(m*\sum_{i=0}^{n-1}strategy[i].size)$ ，空间复杂度为 $O(n*m)$ 或者 $O(m)$ 。
非滚动数组做法：

class Solution {
public:
    /**
     *
     * @param n int整型 n
     * @param m int整型 m
     * @param strategy Point类vector<vector<>> 策略
     * @return int整型
     */
    int producemask(int n, int m, vector<vector<Point> >& strategy) {
        vector<vector<int>>dp(n+1, vector<int>(m+1));
        for(int i=1;i<=n;i++) {
            for(int j=0;j<=m;j++) {
                for(auto x:strategy[i-1]) {
                    if(x.x+j>m) continue;
                    dp[i][j+x.x]=max(dp[i][j+x.x],dp[i-1][j]+x.y);
                }
            }
            for(int j=0;j<=m;j++)dp[i][j]=max(dp[i][j],dp[i-1][j]);//因为本生产线可以不选取任何策略
        }
        return dp[n][m];
    }
};

滚动数组做法：

int producemask(int n, int m, vector<vector<Point> >& strategy) {
        // write code here
        vector<vector<int>>dp(2, vector<int>(m+1));
        for (int i = 0; i < n; i++)
            for (int j = 0; j <= m; j++)
            {
                for (auto& x : strategy[i])
                    if (x.x + j <= m)
                        dp[i & 1][j + x.x] = max(dp[i & 1][j + x.x], dp[1 - i & 1][j] + x.y);
                dp[1-i&1][j]=dp[i&1][j];
            }
        return dp[1-n & 1][m];
    }

做法2：TLE
可以通过枚举每一个产线选取策略几或者不采取策略，然后判断是否可以完成并且对所有情况的口罩数取max。时间复杂度 $O(2^k)$ ，空间复杂度为 $O(n*m+k)$ 。

class Solution {
public:
    /**
     *
     * @param n int整型 n
     * @param m int整型 m
     * @param strategy Point类vector<vector<>> 策略
     * @return int整型
     */
    int a[200001],ans;
    void dfs(int pos,int n,int m,vector<vector<Point> >& k) {
        if(pos==n) {
            int sum=0,have=m;
            for(int i=0;i<n;i++) {
                have-=k[i][a[i]].x;
                sum+=k[i][a[i]].y;
            }
            if(have>=0) ans=max(ans,sum);
            return ;
        }
        for(int i=0;i<k[pos].size();i++) {
            a[pos]=i;
            dfs(pos+1,n,m,k);
        }
    }
    int producemask(int n, int m, vector<vector<Point> >& strategy) {
        for(int i=0;i<strategy.size();i++)
            strategy[i].push_back({0,0});
        dfs(0,n,m,strategy);
        return ans;
    }
};