먼저 가로 방향 울타리의 위치를 정한다. 여기서 가능한 모양의 경우의 수는 $2^{n-1}$일 것이다.
그 다음, 남은 울타리를 세로 방향으로 설치하되 그룹 안 소의 최대 수가 최소가 되도록 설치하는 법을 찾아야 한다.
그룹 안 소의 최대 수를 x라고 하고 이 값에 대해 파라메트릭 서치를 한다. 농장의 왼쪽 열부터 보면서 그룹 안 소의 최대 수가 x이하가 되도록 세로로 울타리를 세웠을 때 모든 울타리 수가 k개 이하인지 판단하는 문제로 바꿔 풀 수 있다.
시간복잡도는 $O(2^{n/2}*n^2*\lg L)$
#include<cstdio> int n, k, s[16][16], a[16], sz, mid, res = 1e9; bool f() { int t = 0, cnt = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= sz; j++) while (s[a[j]][i] - s[a[j]][t] - s[a[j - 1]][i] + s[a[j - 1]][t] > mid) { if (t == i - 1) return false; t = i - 1, cnt++; } } return cnt <= k - sz + 1; } int main() { scanf("%d%d", &n, &k); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { scanf("%d", s[i] + j); s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]; } for (int i = 1 << n - 1; i--;) { sz = 0; for (int j = 0; j < n - 1; j++) if (1 << j&i) a[++sz] = j + 1; a[++sz] = n; int low = 0, up = 1e6; while (low <= up) { mid = low + up >> 1; f() ? up = mid - 1 : low = mid + 1; } if (res > up) res = low; } printf("%d", res); return 0; }
