結果

問題 No.2473 Fraises dans une boîte
コンテスト
ユーザー 👑 SPD_9X2
提出日時 2023-07-17 21:21:12
言語 PyPy3
(7.3.15)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,442 bytes
コンパイル時間 254 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 83,732 KB
最終ジャッジ日時 2024-11-07 08:40:50
合計ジャッジ時間 25,262 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 36 RE * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

Fraises dans une boîte(6) 想定解

6乗ver

"""

import sys
from sys import stdin

H,W = map(int,stdin.readline().split())

S = [list(map(int,stdin.readline().split())) for i in range(H)]

# 制約チェック
assert 1 <= H <= 22
assert 1 <= W <= 22
assert len(S) == H
for s in S:
    assert len(s) == W
    for i in s:
        assert i == 0 or i == 1

# 領域の和を高速に導出するための2次元累積和
SSum = [[0] * (W+1) for i in range(H+1)]
for i in range(H):
    for j in range(W):
        SSum[i+1][j+1] += S[i][j]
for i in range(H):
    for j in range(W+1):
        SSum[i+1][j] += SSum[i][j]
for i in range(H+1):
    for j in range(W):
        SSum[i][j+1] += SSum[i][j]

# メモ化用の4次元list
inf = float("inf")
lis = [[[[0] * (W+1) for i in range(W+1)] for j in range(H+1)] for k in range(H+1)]

# ここからdp
for hsize in range(1,H+1): #縦のサイズが小さい領域から調べる

    for wsize in range(1,W+1): #横のサイズが小さい領域から調べる

        for x1 in range(H): #左上のx座標

            x2 = x1 + hsize
            if x2 > H:
                break
            
            for y1 in range(W): #左上のy座標

                y2 = y1 + wsize
                if y2 > W:
                    break

                # ここから、最小値の導出処理

                now_ans = inf

                # 左上領域の空行カウント用の配列
                zerox = [0]
                zeroy = [0]

                for tmpx in range(x1,x2):
                    nsum = 0
                    for tmpy in range(y1,y2):
                        nsum += S[tmpx][tmpy]
                    if nsum == 0:
                        pl = 1
                    else:
                        pl = 0
                    zerox.append(zerox[-1] + pl)

                for tmpy in range(y1,y2):
                    nsum = 0
                    for tmpx in range(x1,x2):
                        nsum += S[tmpx][tmpy]
                    if nsum == 0:
                        pl = 1
                    else:
                        pl = 0
                    zeroy.append(zeroy[-1] + pl)

                #print (zerox,zeroy)

                for xmid in range(x1,x2+1):

                    for ymid in range(y1,y2+1):

                        #右下が0で無い場合、駄目
                        if SSum[x2][y2] - SSum[xmid][y2] - SSum[x2][ymid] + SSum[xmid][ymid] != 0:
                            continue
                        #左上・右下共に0の場合は推移の意味が無いのでダメ
                        if (xmid-x1) * (ymid-y1) == 0 and (x2-xmid) * (y2-ymid) == 0:
                            continue

                        cost = 0

                        # 左上区間の1の個数
                        lu1 = SSum[xmid][ymid] - SSum[xmid][y1] - SSum[x1][ymid] + SSum[x1][y1]
                        cost += (xmid-x1-zerox[xmid-x1]) * (ymid-y1-zeroy[ymid-y1]) - lu1

                        # 左下と右上
                        cost += lis[xmid][x2][y1][ymid] + lis[x1][xmid][ymid][y2]

                        # デバッグ用
                        #print (x1,xmid,x2,y1,ymid,y2,cost)

                        now_ans = min(now_ans , cost)
                        
                lis[x1][x2][y1][y2] = now_ans

                # デバッグ用
                #print (x1,x2,y1,y2,now_ans)


print (lis[0][H][0][W])
0