사용자 도구

사이트 도구


ps:problems:boj:23318

행렬분할

ps
링크acmicpc.net/…
출처BOJ
문제 번호23318
문제명행렬분할
레벨골드 5
분류

파라메트릭 서치

시간복잡도O(2^m*nmlog(nmK))
인풋사이즈n<=20, m<=8, K<=15
사용한 언어Python
제출기록34576KB / 116ms
최고기록76ms
해결날짜2022/10/07

풀이

코드

"""Solution code for "BOJ 23318. 행렬분할".

- Problem link: https://www.acmicpc.net/problem/23318
- Solution link: http://www.teferi.net/ps/problems/boj/23318

Tags: [Parametric search]
"""

import itertools
import functools
from teflib import binsearch

INF = float('inf')


def can_divide(sum_limit, remaining_div_count, mat):
    sums = [0] * (len(mat[0]))
    for nums in mat:
        sums = [s + n for s, n in zip(sums, nums)]
        if any(s > sum_limit for s in sums):
            if any(n > sum_limit for n in nums):
                return False
            sums = nums
            remaining_div_count -= 1
            if remaining_div_count < 0:
                return False
    return True


def main():
    n, m = [int(x) for x in input().split()]
    a, b = [int(x) for x in input().split()]
    mat = [[int(x) for x in input().split()] for _ in range(n)]

    all_sum = sum(sum(row) for row in mat)
    answer = INF
    for partition in itertools.combinations(range(1, m), b):
        partition = (0, *partition, m)
        new_mat = [[
            sum(row[beg:end]) for beg, end in itertools.pairwise(partition)
        ] for row in mat]
        pred = functools.partial(can_divide, remaining_div_count=a, mat=new_mat)
        min_score = binsearch.minimum_valid_integer(0, all_sum, pred)
        answer = min(answer, min_score)

    print(answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
R S E T E
 
ps/problems/boj/23318.txt · 마지막으로 수정됨: 2022/10/07 17:21 저자 teferi