[python]白駿15724州指数(DP)

📌 質問する

ニモ王国の王・陳京大王は、王国の領土を容易に支配するため、1 X 1の単位区域を複数に組み合わせ、巨大な行政区域である地州数位を構成する計画だ.秦の始皇帝は地主を作るために、一定の矩形の範囲で生活している人数を参考資料にしたいと思っていました.

真京大王はとても厳格な王なので、矩形の範囲を4つの数字で教えてくれます.
例えば、上に人が住んでいると仮定して、「図1」の矩形の範囲内の人数を知りたいなら、陳京大王は4つの整数1、3、2を歌うことができます.同様に、<図2>は1 1 1 1 1 4であり、<図3>は1 1 1 4である.
真京大王のためにこの参考資料を作成するプログラムです.

入力

第1行は領土の大きさN,M(1≦N,M≦1024)を与える.
次のN行はM個の整数で、単位区域内に住む人数です.単位区域ごとに居住する人数は100人以下で、単位区域ごとに少なくとも1人が居住している.
次の行は真京大王好奇心人口数の矩形範囲の個数K(1≦K≦100000)を与える.
以下のK行には、矩形範囲x 1、y 1、x 2、y 2(x 1≦x 2、y 1≦y 2)の4つの整数がある.

しゅつりょく

所定の矩形範囲に生息する人数の和を順次出力する.

入力例1

4 4
9 14 29 7
1 31 6 13
21 26 40 16
8 38 11 23
3
1 1 3 2
1 1 1 4
1 1 4 4

サンプル出力1

102
59
293

📌 に答える

💬 Code

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
dp = [list(map(int, input().split())) for _ in range(n)]

for i in range(1, n):
    for j in range(m):
        dp[i][j] += dp[i-1][j]  # 열별로 합 누적시키기

for _ in range(int(input())):
    fromX, fromY, toX, toY = map(int, input().split())
    ans = sum(dp[toX-1][fromY-1:toY])
    if fromX > 1:
        ans -= sum(dp[fromX-2][fromY-1:toY])
    print(ans)

💡 Solution

 9 14 29  7   →    9  14 29  7
 1 31  6 13   →   10  45 35 20
21 26 40 16   →   31  71 75 36
 8 38 11 23   →   39 109 86 59

列ごとに累加する.最後の行39は第1列の和、109は第2列の和、86は第3列の和、59は第4列の和である.

1 1 3 2 (입력)   →   102 (출력)
1 1 1 4 (입력)   →   59 (출력)
2 2 3 4 (입력)   →   132 (출력)
3 2 4 4 (입력)   →   154 (출력)

上の矩形が入力された様子、下の矩形が列ごとに加算された様子.
ピンクを塗ったように一番下の線和を求めると正解が得られ、2 2 3 4のようにエリアが真ん中から始まる場合、一番下の線と最初の場所2行から1行の1行の和を抜いて正解が得られます.
右王第二次短符号化ランキング