3219. 切蛋糕的最小总开销 II

Powered by:NEFU AB-IN

Link

3219. 切蛋糕的最小总开销 II

题意

这道题的核心是将一个 m x n 的矩形蛋糕切成 1 x 1 的小块，使得总切割开销最小

思路

1. dfs + 记忆化搜索

   过不了大样例，但思路比较好想。就是dfs切哪里，如果一个地方切了，就递归下两个状态，因为切了一刀，一定会转变为两个块
   状态一开始是从左上角切到右下角，当相等时，就是切完了

2. 贪心

   1. 将水平和垂直切割费用分别从大到小排序。排序的原因是我们希望优先选择较大的切割费用来尽早切割，这样能够最大化每次切割的增量价值
   2. 使用两个指针分别遍历水平和垂直切割费用，维护当前的水平和垂直切割数量，每次选择当前最小的切割开销进行切割，并更新总成本和切割数量
   3. 当一个方向的切割费用处理完毕后，处理剩余的另一方向的切割费用

代码

'''
Author: NEFU AB-IN
Date: 2024-07-14 10:28:41
FilePath: \LeetCode\CP406\c\c.py
LastEditTime: 2024-07-14 11:14:43
'''
# 3.8.19 import
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, comb, fabs, floor, gcd, log, perm, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Dict, List, Tuple, TypeVar, Union

# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)

# Set recursion limit
setrecursionlimit(int(2e9))


class Arr:
    array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
    graph = staticmethod(lambda size=N: [[] for _ in range(size)])


class Math:
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)


class IO:
    input = staticmethod(lambda: stdin.readline().rstrip("\r\n"))
    read = staticmethod(lambda: map(int, IO.input().split()))
    read_list = staticmethod(lambda: list(IO.read()))


class Std:
    pass

# ————————————————————— Division line ——————————————————————


class Solution:
    def minimumCost(self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int]) -> int:
        @lru_cache(None)
        def dfs(r1, c1, r2, c2):
            if r1 == r2 and c1 == c2:
                return 0

            min_cost = INF

            for i in range(r1, r2):
                cost = horizontalCut[i] + dfs(r1, c1, i, c2) + dfs(i + 1, c1, r2, c2)
                min_cost = Math.min(min_cost, cost)

            for j in range(c1, c2):
                cost = verticalCut[j] + dfs(r1, c1, r2, j) + dfs(r1, j + 1, r2, c2)
                min_cost = Math.min(min_cost, cost)

            return min_cost

        return dfs(0, 0, m - 1, n - 1)


print(Solution().minimumCost(3, 2, [1, 3], [5]))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

'''
Author: NEFU AB-IN
Date: 2024-07-14 10:28:41
FilePath: \LeetCode\CP406\d\d.py
LastEditTime: 2024-07-14 11:39:59
'''
# 3.8.19 import
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, comb, fabs, floor, gcd, log, perm, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Dict, List, Tuple, TypeVar, Union

# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)

# Set recursion limit
setrecursionlimit(int(2e9))


class Arr:
    array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
    graph = staticmethod(lambda size=N: [[] for _ in range(size)])


class Math:
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)


class IO:
    input = staticmethod(lambda: stdin.readline().rstrip("\r\n"))
    read = staticmethod(lambda: map(int, IO.input().split()))
    read_list = staticmethod(lambda: list(IO.read()))


class Std:
    pass

# ————————————————————— Division line ——————————————————————


class Solution:
    def minimumCost(self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int]) -> int:
        horizontalCut.sort(reverse=True)
        verticalCut.sort(reverse=True)

        total_cost = 0
        h_slices = 1
        v_slices = 1

        h_index, v_index = 0, 0

        while h_index < len(horizontalCut) and v_index < len(verticalCut):
            if horizontalCut[h_index] >= verticalCut[v_index]:
                total_cost += horizontalCut[h_index] * v_slices
                h_slices += 1
                h_index += 1
            else:
                total_cost += verticalCut[v_index] * h_slices
                v_slices += 1
                v_index += 1

        while h_index < len(horizontalCut):
            total_cost += horizontalCut[h_index] * v_slices
            h_slices += 1
            h_index += 1

        while v_index < len(verticalCut):
            total_cost += verticalCut[v_index] * h_slices
            v_slices += 1
            v_index += 1

        return total_cost


solution = Solution()

test_cases = [
    (6, 3, [2, 3, 2, 3, 1], [1, 2])
]

results = [solution.minimumCost(*case) for case in test_cases]
print(results)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95