[白俊](C++)11660-区間と5を求めます

BOJシルバー11660号
N*Nテーブルに数字を記入し、特定範囲内の数字の和を求める問題.

質問する

11660区間加算5

に近づく

最初に、2 D配列のすべての数値を加算し、入力範囲内のすべての数値を加算します.
その結果,時間的複雑度がO(N^2)であったため,タイムアウトに失敗した.
アルゴリズム分類が動的プログラミングの場合、(1,1)格子から(i,j)格子までの範囲の数値の和を覚えてほしいというヒントが得られました.

上図では、グレーの範囲の数字は(青の範囲+赤の範囲-緑の範囲)と同じです.
各範囲の数字の和は、図に表示されるカラーセルに格納されます.
2 D配列を入力するときは、(1、1)セルの数値の和を覚えておいてください.数値を保存するのではありません.

問題を解く

2 D配列を初めて受け入れる場合は、以下のプレースホルダを使用します.

map[i][j] = map[i][j - 1] + map[i - 1][j] - map[i - 1][j - 1] + tmp

// tmp = 해당 칸의 숫자라고 입력받은 수

特定区間の和を下図に示す.

上図では、黒の範囲の数字は(青-赤-黄+緑)と同じです.
従って、使用点火式は以下の通りである.

ans = map[x2][y2] - map[x1 - 1][y2] - 
	map[y1 - 1][x2] + map[x1 - 1][y1 - 1]

2つの点火式でコードを記述します.

#include <iostream>
using namespace std;

int map[1026][1026];
int n, m;
int x1, x2, y1, y2;
int tmp;

int main()
{
	ios::sync_with_stdio(0);
    	cin.tie(NULL); cout.tie(NULL);
    
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
		{
			cin >> tmp;
			map[i][j] = tmp + map[i][j - 1] + map[i - 1][j] - map[i - 1][j - 1];
		}
	while (m--)
	{
		cin >> x1 >> y1 >> x2 >> y2;
		cout << map[x2][y2] - map[x1 - 1][y2] - map[x2][y1 - 1] + map[x1 - 1][y1 - 1] << '\n';
	}
	return 0;
}

I/O例

4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4

27
6
64

2 4
1 2
3 4
1 1 1 1
1 2 1 2
2 1 2 1
2 2 2 2

1
2
3
4