[白俊](C++)11660-区間と5を求めます
2077 ワード
BOJシルバー11660号
N*Nテーブルに数字を記入し、特定範囲内の数字の和を求める問題.
11660区間加算5
最初に、2 D配列のすべての数値を加算し、入力範囲内のすべての数値を加算します.
その結果,時間的複雑度がO(N^2)であったため,タイムアウトに失敗した.
アルゴリズム分類が動的プログラミングの場合、(1,1)格子から(i,j)格子までの範囲の数値の和を覚えてほしいというヒントが得られました.
上図では、グレーの範囲の数字は(青の範囲+赤の範囲-緑の範囲)と同じです.
各範囲の数字の和は、図に表示されるカラーセルに格納されます.
2 D配列を入力するときは、(1、1)セルの数値の和を覚えておいてください.数値を保存するのではありません.
2 D配列を初めて受け入れる場合は、以下のプレースホルダを使用します. 特定区間の和を下図に示す.
上図では、黒の範囲の数字は(青-赤-黄+緑)と同じです.
従って、使用点火式は以下の通りである. 2つの点火式でコードを記述します.
N*Nテーブルに数字を記入し、特定範囲内の数字の和を求める問題.
質問する
11660区間加算5
に近づく
最初に、2 D配列のすべての数値を加算し、入力範囲内のすべての数値を加算します.
その結果,時間的複雑度がO(N^2)であったため,タイムアウトに失敗した.
アルゴリズム分類が動的プログラミングの場合、(1,1)格子から(i,j)格子までの範囲の数値の和を覚えてほしいというヒントが得られました.
上図では、グレーの範囲の数字は(青の範囲+赤の範囲-緑の範囲)と同じです.
各範囲の数字の和は、図に表示されるカラーセルに格納されます.
2 D配列を入力するときは、(1、1)セルの数値の和を覚えておいてください.数値を保存するのではありません.
問題を解く
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]
#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
Reference
この問題について([白俊](C++)11660-区間と5を求めます), 我々は、より多くの情報をここで見つけました https://velog.io/@venniek/백준C-11660-구간-합-구하기-5テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol