题意

最小切割刀数，使得最后切割完的矩形的$1 \leq K$

思路

首先可以注意到 $H$ 很小。我们可以通过暴力枚举 $2^H$ 枚举所有横着切的方案，当我们确定横着切了多少刀的时候，纵的方案可以贪心，每次尽量靠后切。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll N, M, K, L, R, H, W;
    cin >> H >> W >> K;
    vector<string> s(H);
    for (auto &i : s)
        cin >> i;
    int ans = 0x3f3f3f3f;
    for (int i = 0; i < 1 << (H - 1); i++)
    {
        vector<vector<int>> bag;
        vector<int> c;
        c.push_back(0);
        for (int j = 0; j < H - 1; j++)
        {
            if ((i >> j) & 1)
            {
                bag.push_back(c);
                c.clear();
                c.push_back(j + 1);
            }
            else
            {
                c.push_back(j + 1);
            }
        }
        bag.push_back(c);
        vector<int> num(bag.size());
        int box = bag.size() - 1;
        for (int j = 0; j < W; j++)
        {
            vector<int> add(bag.size());
            for (int k = 0; k < bag.size(); k++)
            {
                for (auto l : bag[k])
                {
                    if (s[l][j] == '1')
                        add[k]++;
                }
            }
            bool flag = true;
            for (int k = 0; k < bag.size(); k++)
            {
                if (num[k] + add[k] > K)
                {
                    flag = false;
                }
                if (add[k] > K)
                {
                    box = 0x3f3f3f3f;
                    flag = false;
                }
            }
            if (flag)
            {
                for (int k = 0; k < bag.size(); k++)
                {
                    num[k] += add[k];
                }
            }
            else
            {
                box++;
                num = add;
            }
        }
        ans = min(ans, box);
    }
    cout << ans << endl;
    return 0;
}