[白準11660]区間と5❗を求めます
14998 ワード
🥚質問リンク
https://www.acmicpc.net/problem/11660
🍳コード#コード#
1.prefix sum[r][c]には、r行の1番目からcまでの数字の和が格納される。
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
arr = [[0]*(N+1)] + [[0] + list(map(int, input().split())) for _ in range(N)]
# 누적합
# prefix_sum[r][c]: r행의 1번째 열의 숫자부터 c번째 열의 숫자까지의 합
prefix_sum = [[0]*(N+1) for _ in range(N+1)]
for r in range(1, N+1):
for c in range(1, N+1):
prefix_sum[r][c] = prefix_sum[r][c-1] + arr[r][c]
for _ in range(M):
x1, y1, x2, y2 = map(int, input().split())
ans = 0
for r in range(x1, x2+1):
ans += prefix_sum[r][y2] - prefix_sum[r][y1-1]
print(ans)
2.prefix sum[r][c]に(1,1)から(r,c)までの和を保存する。
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
arr = [[0]*(N+1)] + [[0] + list(map(int, input().split())) for _ in range(N)]
# 누적합
# prefix_sum[r][c]: (1, 1,)부터 (r, c)까지의 합
prefix_sum = [[0]*(N+1) for _ in range(N+1)]
for r in range(1, N+1):
for c in range(1, N+1):
prefix_sum[r][c] = prefix_sum[r-1][c] + \
prefix_sum[r][c-1] - prefix_sum[r-1][c-1] + arr[r][c]
for _ in range(M):
x1, y1, x2, y2 = map(int, input().split())
ans = prefix_sum[x2][y2] - prefix_sum[x2][y1-1] - \
prefix_sum[x1-1][y2] + prefix_sum[x1-1][y1-1]
print(ans)
🧂アイデア
累計和,DP
1.prefix sum[r][c]には、r行の1番目からcまでの数字の和が格納される。
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
arr = [[0]*(N+1)] + [[0] + list(map(int, input().split())) for _ in range(N)]
# 누적합
# prefix_sum[r][c]: r행의 1번째 열의 숫자부터 c번째 열의 숫자까지의 합
prefix_sum = [[0]*(N+1) for _ in range(N+1)]
for r in range(1, N+1):
for c in range(1, N+1):
prefix_sum[r][c] = prefix_sum[r][c-1] + arr[r][c]
for _ in range(M):
x1, y1, x2, y2 = map(int, input().split())
ans = 0
for r in range(x1, x2+1):
ans += prefix_sum[r][y2] - prefix_sum[r][y1-1]
print(ans)
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
arr = [[0]*(N+1)] + [[0] + list(map(int, input().split())) for _ in range(N)]
# 누적합
# prefix_sum[r][c]: (1, 1,)부터 (r, c)까지의 합
prefix_sum = [[0]*(N+1) for _ in range(N+1)]
for r in range(1, N+1):
for c in range(1, N+1):
prefix_sum[r][c] = prefix_sum[r-1][c] + \
prefix_sum[r][c-1] - prefix_sum[r-1][c-1] + arr[r][c]
for _ in range(M):
x1, y1, x2, y2 = map(int, input().split())
ans = prefix_sum[x2][y2] - prefix_sum[x2][y1-1] - \
prefix_sum[x1-1][y2] + prefix_sum[x1-1][y1-1]
print(ans)
累計和,DP
1.prefix sum[r][c]には、r行の1番目からcまでの数字の和が格納される。
2.prefix sum[r][c]に(1,1)から(r,c)までの和を保存する。
注意:https://claude-u.tistory.com/427
Reference
この問題について([白準11660]区間と5❗を求めます), 我々は、より多くの情報をここで見つけました https://velog.io/@eastgloss0330/백준-11660-구간-합-구하기-5テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol