Edit

【pythonでABC005を解説】D - おいしいたこ焼きの焼き方

問題概要

問題ページ

D - おいしいたこ焼きの焼き方
D - おいしいたこ焼きの焼き方

問題ページへ移動する


高橋君のたこ焼き屋で使っているたこ焼き器は焼く場所によって美味しさの変わるクセの強いたこ焼き器です。
また、店員の力量によって一度に焼けるたこ焼きの数が違います。
高橋君はそれぞれの店員ができるだけ美味しくたこ焼きを焼けるようにしようと思いました。

たこ焼き器は\(N×N\)の正方形をしています。
それぞれの場所ごとにたこ焼きの美味しさ\(D_{ij}\)が決まっています。
それぞれの店員は一度に焼けるたこ焼きの上限\(P_k\)が決まっています。
また、一度に焼くたこ焼きは必ずたこ焼き器の長方形の部分になっていて、その中の全てを使わなければなりません。
それぞれの店員について一度に焼けるたこ焼きの美味しさの合計の最大値を求めて下さい。
ただし、店員が焼き始める時はたこ焼き器が完全に空いていてどの場所でも使えるとします。

入力は以下の形式で標準入力から与えられる。

\(N\)
\(D_{11}\) \(D_{12}\) ... \(D_{1N}\)
\(D_{21}\) \(D_{22}\) ... \(D_{2N}\)
\(...\)
\(D_{N1}\) \(D_{N2}\) ... \(D_{NN}\)
\(Q\)
\(P_1\)
\(P_2\)
\(...\)
\(P_Q\)
  • １行目にたこ焼き器の一辺の大きさを表す整数\(N(1≦N≦50)\)が与えられます。
  • 続く\(N\)行にたこ焼き器のそれぞれの場所で焼けるたこ焼きの美味しさを表す整数\(D_{ij}(1≦D_{ij}≦100)\)が与えられます。
  • 次の行に店員の人数を表す整数\(Q\)(\(1≦Q≦N^2\))が与えられます。
  • 続く\(Q\)行にそれぞれの店員が焼けるたこ焼きの数を表す整数\(P_k(1≦P_k≦N^2)\)が与えられます。

それぞれの店員について一度に焼けるたこ焼きの美味しさの合計の最大値を出力して下さい。
また、出力の末尾には改行を入れて下さい。

問題の考察

ACコード

import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    ls = [[0] * (n + 1)]
    for i in range(n):
        d = list(map(int, input().rstrip('\n').split()))
        ls.append([0] + d)
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            ls[i][j] += ls[i][j-1] + ls[i-1][j] - ls[i-1][j-1]
    d = collections.defaultdict(int)
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            for k in range(i - 1, -1, -1):
                for l in range(j - 1, -1, -1):
                    cnt = (i - k) * (j - l)
                    o = ls[i][j] - ls[i][l] - ls[k][j] + ls[k][l]
                    d[cnt] = max(d[cnt], o)
    for i in range(n ** 2):
        d[i + 1] = max(d[i + 1], d[i])
    q = int(input().rstrip('\n'))
    for i in range(q):
        p = int(input().rstrip('\n'))
        print(d[p])


if __name__ == '__main__':
    solve()

-Edit
-