给墙壁刷油漆

题目

2742. 给墙壁刷油漆

---

给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time ，分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠：

• 一位需要 付费 的油漆匠，刷第 i 堵墙需要花费 time[i] 单位的时间，开销为 cost[i] 单位的钱。
• 一位 免费 的油漆匠，刷 任意 一堵墙的时间为 1 单位，开销为 0 。但是必须在付费油漆匠 工作 时，免费油漆匠才会工作。

请你返回刷完 n 堵墙最少开销为多少。

示例 1：

输入：cost = [1,2,3,2], time = [1,2,3,2]
输出：3
解释：下标为 0 和 1 的墙由付费油漆匠来刷，需要 3 单位时间。同时，免费油漆匠刷下标为 2 和 3 的墙，需要 2 单位时间，开销为 0 。总开销为 1 + 2 = 3 。

示例 2：

输入：cost = [2,3,4,2], time = [1,1,1,1]
输出：4
解释：下标为 0 和 3 的墙由付费油漆匠来刷，需要 2 单位时间。同时，免费油漆匠刷下标为 1 和 2 的墙，需要 2 单位时间，开销为 0 。总开销为 2 + 2 = 4 。

提示：

• 1 <= cost.length <= 500
• cost.length == time.length
• 1 <= cost[i] <= 10^6
• 1 <= time[i] <= 500

题解

方法一：

思路

转化成01背包。

只要付费刷墙的时间>=非付费刷墙的个数，在这种情况下花的时间越少越好。

转化一下，付费刷墙的时间+付费刷墙的个数>=n的情况下，所花的最小费用。

可以让每面墙所花时间+1.

定义$f_{i,j}$为前i面墙至少花费j时间的最小费用。

那么$f_{i,j} = max(f_{i-1, j-time_i-1}+cost_i, f_{i-1, j})$

$f_{i,j} = \left\lbrace \begin{array}{ll}
0 & j<0 \
INF & i=-1, j>0
\end{array} \right.$

代码

class Solution {
public:
    /*
        付费刷墙的时间 >= n-付费墙个数
        付费墙的时间+付费墙的个数>=n
        每面付费墙的所需时间都+1
        f_{i,j} 前i面墙，花时间至少为j的最小花销。
        f_{i,j} = min(f_{i-1,j-time[i]-1}+cost[i], f_{i-1, j})
    */
    const int INF = 0x3f3f3f3f;
    int paintWalls(vector<int>& cost, vector<int>& time) {
        // int f[505][505];
        // memset(f, -1, sizeof(f));
        // function<int(int,int)> dfs = [&](int i, int j) {
        //     if (j<=0) return 0;
        //     if (i<0) return INF;
        //     if (f[i][j] != -1) return f[i][j];
        //     return f[i][j] = min(dfs(i-1, j-time[i]-1) + cost[i], dfs(i-1, j));
        // };
        // return dfs(cost.size()-1, cost.size());
        int f[505][505];
        memset(f, 0x3f, sizeof(f));
        f[0][0] = 0;
        int n = cost.size();
        for (int i=1; i<=n; i++) {
            for (int j=0; j<=n; j++) {
                f[i][j] = min(f[i-1][max(0, j-time[i-1]-1)]+cost[i-1], f[i-1][j]);
            }
        }
        return f[n][n];
    }
};

方法二：

思路

定义$f_{i,j,k}$ 前i面墙，刷了免费费j面，所用付费时间为k的最小花销。 空间和时间都超出。

用c=k-j代替i和k，定义$f_{i,c}$为前i面墙，付费时间-免费时间至少为c，所需最小的花费。

显然当c大于剩余要刷的墙时，剩余的墙都可以免费刷。

$f_{i,c} = max(f_{i-1, c+time_i}+cost_i, f_{i-1, c-1})$

$f_{i,c} = \left\lbrace \begin{array}{ll} 0 & c\ge i+1 \ INF & i=-1, c>0 \end{array} \right.$

代码

class Solution {
public:
    /*
        f_{i,j,k} 前i面墙，刷了免费费j面，所用付费时间为k的最小花销。 超时
        当k>=j时是合法的。用c=k-j代替i和k，将状态变为2维。
        f_{i,c} = min(f_{i-1, c+time[i]}+cost[i], f_{i-1, c-1})
    */
    const int INF = 0x3f3f3f3f;
    int paintWalls(vector<int>& cost, vector<int>& time) {
        int f[505][1015];
        memset(f, -1, sizeof(f));
        function<int(int,int)> dfs = [&](int i, int j) {
            if (j>=i+1) return 0;
            if (i<0) return INF;
            if (f[i][j+505] != -1) return f[i][j+505];
            return f[i][j+505] = min(dfs(i-1, j+time[i])+cost[i], dfs(i-1, j-1));
        };
        return dfs(cost.size()-1, 0);
    }
};