水博客真开心

1. 题目

传送门=￣ω￣=

2. 题解

先二分答案，然后 $2 ^ n$枚举怎么切割行，然后再扫描列的切割。

扫描列的切割有些小细节需要注意一下。

代码：

#include <bits/stdc++.h>

#define NS (20)

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, k, d[NS][NS], lim;

bool book[NS];

bool Chk(int rem)
{
    int sum[NS][NS], cnt = 1, tot[NS];
    memset(sum, 0, sizeof(sum)), memset(tot, 0, sizeof(tot));
    for (int i = 1; i <= n; i += 1)
    {
        for (int j = 1; j <= n; j += 1) sum[cnt][j] += d[i][j];
        if (book[i]) cnt++;
    }
    for (int i = 1; i <= n; i += 1)
    {
        int mx = 0;
        for (int j = 1; j <= cnt; j += 1)
        {
            if (sum[j][i] > lim) return 0;
            tot[j] += sum[j][i], mx = max(mx, tot[j]);
        }
        if (mx > lim)
        {
            if (!rem) return 0;
            rem--;
            for (int j = 1; j <= cnt; j += 1)
                tot[j] = sum[j][i];
        }
    }
    return 1;
}

bool Jud(int a, int rem)
{
    if (a >= n) return Chk(rem);
    if (rem)
    {
        book[a] = 1;
        if (Jud(a + 1, rem - 1)) return 1;
    }
    book[a] = 0;
    if (Jud(a + 1, rem)) return 1;
    return 0;
}

int main(int argc, char const* argv[])
{
    IN(n), IN(k);
    int l = 0, r = 0;
    for (int i = 1; i <= n; i += 1)
        for (int j = 1; j <= n; j += 1)
            IN(d[i][j]), l = max(l, d[i][j]), r += d[i][j];
    while (l < r)
    {
        lim = (l + r) >> 1;
        if (Jud(1, k)) r = lim;
        else l = lim + 1;
    }
    printf("%d\n", l);
    return 0;
}