📚 1451-長方形に分割

長方形に分割

理解する

勘定科目の合計(1,1)~(n,m)
各席合計
(1,1)~(2,2)の総和
(2, 2) = (1, 2) + (2, 1) - (1, 1)
→なぜ(1,1)を外しますか?(1,2)と(2,1)に(1,2)を加える.
 
(2,2)~(3,3)までの総和
(3, 3) = (2, 3) + (3, 2) - (2, 2)
→なぜ(2,2)を外しますか?(2,3)と(3,2)に(2,2)を加えて2回.
ex)
既存のマトリクス
1365781078
 
(1,1)行から(n,m)行列までの総和.
|1|4|10|
|-|-|-|
|6|16|30|
|16|33|55|
 
次のようにします.
現在の(1,1)行列から(3,3)行列までは和で構成されている.
14(1+3)10(1+3+6)6(1+5)16(7+5+3+1)3016(1+5+10)3355
(2,2)から(3,3)までの合計はいくらですか.
(1,1)から見始めたとき
(2,2)~(3,3)以外の部分は外します.
xxxxx
でも考えてみれば.

(1, 1) ~ (3, 1)の合計は(3, 1)に格納される.

(1, 1) ~ (1, 3)の合計は(1, 3)に格納される.

だから55(3, 3) - 16(3, 1) - 10(1, 3) + 1(1, 1)→なぜ1(1, 1)→見て、(3, 1)統合で増加(1, 1)、(1, 3)統合で増加(1, 1).よって、(1, 1)2回減じ、必要+1(1, 1).
 
テストソース

arr = [[0, 1, 3, 6], [0, 5, 7, 8],[0, 10,7,8]]

print(sum(arr[0]) + sum(arr[1]))

result = [[0] * 5 for _ in range(5)]

arr = [[0]] + arr

print("arr : ", arr)

for i in range(1, 4):
    for j in range(1, 4):
        result[i][j] = result[i - 1][j] + result[i][j - 1] - result[i - 1][j - 1] + arr[i][j]


def sum_cal(x1, y1, x2, y2):
    print(result[x2][y2], result[x2][y1 - 1], result[x1 - 1][y2], result[x1 - 1][y1 - 1])
    return result[x2][y2] - result[x2][y1 - 1] - result[x1 - 1][y2] + result[x1 - 1][y1 - 1]


print("result : ", result)
print(sum_cal(2, 2, 3, 3))

 
結果

30
arr :  [[0], [0, 1, 3, 6], [0, 5, 7, 8], [0, 10, 7, 8]]
result :  [[0, 0, 0, 0, 0], [0, 1, 4, 10, 0], [0, 6, 16, 30, 0], [0, 16, 33, 55, 0], [0, 0, 0, 0, 0]]
55 16 10 1
30

 
✔¥矩形が3つに分かれている場合
(1)
|o|x|t|
|-|-|-|-|
|o|x|t|

(1, 1) ~ (n, i)

(1, i+1) ~ (n, j)

(1, j+1) ~ (n, m)

(2)
|o|o|
|-|-|-|-|
|x|x|
|t|t|

(1, 1) ~ (i, m)

(i+1, 1) ~ (j, m)

(j+1, 1) ~ (n, m)

(3)
|o|x|x|
|-|-|-|-|
|o|t|t|

(1, 1) ~ (n, i)

(1, i+1) ~ (j, m)

(j+1, i+1) ~ (n, m)

(4)
|o|o|x|
|-|-|-|-|
|t|t|x|

(1, 1) ~ (i, j)

(i+1, 1) ~ (n, j)

(1, j+1) ~ (n, m)

(5)
|o|o|
|-|-|-|-|
|x|t|
|x|t|

(1, 1) ~ (i, m)

(i+1, 1) ~ (n, j)

(i+1, j+1) ~ (n, m)

(6)
|o|x|
|-|-|-|-|
|o|x|
|t|t|

(1, 1) ~ (i, j)

(1, j+1) ~ (i, m)

(i+1, 1) ~ (n, m)

 

ソース

import sys

read = sys.stdin.readline

n, m = map(int, read().split())

arr = [[0] * (m + 1)]

for i in range(n):
    arr.append([0] + list(map(int, read().strip())))

sum_rec = [[0] * (m + 1) for _ in range(n + 1)]

# (1, 1)부터 (n, m)까지 각 자리의 총합
for i in range(1, n + 1):
    for j in range(1, m + 1):
        sum_rec[i][j] = arr[i][j] + sum_rec[i - 1][j] + sum_rec[i][j - 1] - sum_rec[i - 1][j - 1]


# 각 자리수 총합을 이용해 (a, b)부터 (n, m)까지 합
def sum_of_rec(x1, y1, x2, y2):
    # print(sum_rec[x2][y2], sum_rec[x1 - 1][y2], sum_rec[x2][y1 - 1], y2)
    return sum_rec[x2][y2] - sum_rec[x1 - 1][y2] - sum_rec[x2][y1 - 1] + sum_rec[x1 - 1][y1 - 1]


result = 0
ans = 0

# (1) 전체 직사각형을 세로로만 분할한 경우
for i in range(1, m - 1):
    for j in range(i + 1, m):
        num1 = sum_of_rec(1, 1, n, i)
        num2 = sum_of_rec(1, i + 1, n, j)
        num3 = sum_of_rec(1, j + 1, n, m)

        if result < num1 * num2 * num3:
            result = num1 * num2 * num3

# (2) 전체 직사각형을 가로로만 분할한 경우
for i in range(1, n - 1):
    for j in range(i + 1, n):
        num1 = sum_of_rec(1, 1, i, m)
        num2 = sum_of_rec(i + 1, 1, j, m)
        num3 = sum_of_rec(j + 1, 1, n, m)

        if result < num1 * num2 * num3:
            result = num1 * num2 * num3

# (3) 전체 세로 분할 후, 우측 가로 분할한 경우
for i in range(1, m):
    for j in range(1, n):
        num1 = sum_of_rec(1, 1, n, i)
        num2 = sum_of_rec(1, i + 1, j, m)
        num3 = sum_of_rec(j + 1, i + 1, n, m)

        if result < num1 * num2 * num3:
            result = num1 * num2 * num3

# (4) 전체 세로 분할 후, 좌측 가로 분할한 경우
for i in range(1, n):
    for j in range(1, m):
        num1 = sum_of_rec(1, 1, i, j)
        num2 = sum_of_rec(i + 1, 1, n, j)
        num3 = sum_of_rec(1, j + 1, n, m)

        if result < num1 * num2 * num3:
            result = num1 * num2 * num3

# (5) 전체 가로 분할 후, 하단 세로 분할한 경우
for i in range(1, n):
    for j in range(1, m):
        num1 = sum_of_rec(1, 1, i, m)
        num2 = sum_of_rec(i + 1, 1, n, j)
        num3 = sum_of_rec(i + 1, j + 1, n, m)

        if result < num1 * num2 * num3:
            result = num1 * num2 * num3

# (6) 전체 가로 분할 후, 상단 세로 분할한 경우
for i in range(1, n):
    for j in range(1, m):
        num1 = sum_of_rec(1, 1, i, j)
        num2 = sum_of_rec(1, j + 1, i, m)
        num3 = sum_of_rec(i + 1, 1, n, m)

        if result < num1 * num2 * num3:
            result = num1 * num2 * num3

print(result)

 
採点結果

 
问题解决には、间违った変数を1つ入力してしまったので、ずっと间违っていました(1位置にiを入力して)、探すのに长い时间がかかりましたが、多くの変数を使っていたら、単独でメモを整理して、ソースを书きましょう!!