杂题——蛋糕划分

蛋糕划分

小度准备切一个蛋糕。这个蛋糕的大小为 NxN*，蛋糕每个部分的重量并不均匀。

小度一共可以切 K 刀，每一刀都是垂直或者水平的，现在小度想知道在切了 K 刀之后，最重的一块蛋糕最轻的重量是多少。

格式

输入格式：

第1行包含N和K。其中：2≤N≤15，1≤K≤2N−2；
第2到第1+N行：每行 N 个数字，描述这一行蛋糕每个位置的重量 W。其中：0≤W≤1000。

输出格式：

输出一个整数，最重的一块蛋糕最轻是多少。

样例 1

输入：

1
2
3
4
3 2
1 1 2
1 1 2
2 2 5

复制

输出：

1
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
78
79
80
81
82
83
84
85
#include<bits/stdc++.h> 

using namespace std;
const int N = 20;
int n, k;
int a[N][N], s[N][N];

int calc(int x1, int y1, int x2, int y2) {
    return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
}

bool check(int val) {
    
    for (int i = 0; i < 1 << (n - 1); i++) {
        // 存放横向的切法
        vector<int> pos;
        // 这个地方很细节
        pos.push_back(0);
        for (int j = 0; j < n - 1; j++) {
            if (i >> j & 1) {
                pos.push_back(j + 1);
            }
        }

        if (pos.size() > k + 1) continue;
        int cnt = pos.size() - 1;
        pos.push_back(n);
        bool flag = true;

        for (int j = 1; j <= n && flag; j++) {
            for (int p = 0; p < pos.size() - 1; p++) {
                int w = calc(pos[p] + 1, j, pos[p + 1], j);
                if (w > val) {
                    flag = false;
                    break;
                }
            }
        }
        if (!flag) continue;

        int last = 1;
        // 枚举钟祥切法
        for (int j = 1; j <= n; j++) {
            for (int p = 0; p < pos.size() - 1; p++) {
                int w = calc(pos[p] + 1, last, pos[p + 1], j);
                if (w > val) {
                    // 如果大于val就在j - 1 的位置切一刀
                    // 下一个查询区间为[j, ?]
                    last = j;
                    cnt ++;
                    break;
                }
            }
        }
        if (cnt <= k) return true;
    }

    return false;
}

int main( )
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
     int l = 0;
    cin >> n >> k;
    // 基本的二维前缀和
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
            l = max(a[i][j], l);
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    }

    // 二分寻找合适的大小
    int r = 2e9;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    cout << r;
    return 0;
}