[アルゴリズム解答]白駿11660区間求和5

今日もデイリーエンコーディング倉庫からランダムに1~4個の数字を抽出して問題を解きました!今日のランダム数字は2番です!
だから今日解決した問題は白駿11660-区間と5を求めますです.

質問する

N×N個数N×nサイズの表に記入します.(x 1,y 1)から(x 2,y 2)までの和を求めるプログラムを記述する.(x,y)はx行y列を表す.
例えば、N=4の場合、表は以下のようになります.

ここで(2,2)から(3,4)までの和は3+4+5+4+5+6=27、(4,4)から(4,4)までの和は7である.
表に和と和を求める演算が与えられている場合は、プロセッサを作成します.

入力

第1行は、テーブルのサイズNと和を求める回数Mを与える.(1≦N≦1024,1≦M≦100000)2行目から、N行目において、1行目から順に表に記入された数字が与えられる.次のM行には、4つの整数x 1、y 1、x 2、y 2があり、(x 1、y 1)から(x 2、y 2)まで加算出力される.表の数字は1000以下の自然数です.(x1 ≤ x2, y1 ≤ y2)

しゅつりょく

M行の合計(x 1,y 1)から(x 2,y 2)へ出力します.

例

入力します。

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

解答方法

問題1の例は次のとおりです.

求められる値は黄色領域の値であり、この値は以下のようにすることができる.

노란 영역의 합 = 초록 영역의 합 - 연보라 영역의 합 - 진보라 영역의 합 + 빨간 동그라미 영역의 합 (1)
// dp[x2][y2] - dp[x1][y2] - dp[x2][y1] + dp[x1][y1];

すなわち,値(1,1)~(i,j)領域の総和を求めるために依然として用いられている.
従って、新しいN*Nアレイ(dpアレイと呼ぶ!)中(i,j)に(1,1)から(i,j)までの領域の総和を格納すると、必要な値を直接インポートして計算することができます!
(この操作を行う前に、単純な重複文の開始と終了条件を調整するだけでいいかもしれませんが、入力値の範囲が広く、M個のエンクロージャの値を求める必要があるため、重複計算を減らす必要があるので、dpを思い出しました!)
また,マザーボードにナビゲートしてdpを充填する場合,以前に求めたdp値を用いたため,dpをより決定できる.

すなわち、上図では、dp[3][3]すなわち黄色領域の和を以下に示すことができる.

노란 영역의 합 = 보라 영역의 합 + 초록 영역의 합 - 빨간 영역의 합 + 현재 좌표의 보드 값 (2)
// dp[i][j] = dp[i-1][j] + dp[i][j-1] + board[i][j] - dp[i-1][j-1];

このとき,紫色領域の和,緑色領域の和,赤色領域の和を求めたが,現在座標の板値も直接得ることができる!
また、上記のようにdpを充填する場合、(1,1)から一貫した形で充填するために、0行0列をすべて0に初期化する手順が以下のように加えられている.

整理後(2)番号方式でdpを初期化し、(1)番号方式で結果を求めればよい!

コード#コード#

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // reader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); // writer
        StringTokenizer st; // tokenizer

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[][] board = new int[n+1][n+1];
        for(int i=1; i<=n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=n; j++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 초기값
        int[][] dp = new int[n+1][n+1];
        dp[0][0] = 0;
        for(int i=1; i<=n; i++){
            dp[0][i] = 0;
            dp[i][0] = 0;
        }
        // init dp
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1] + board[i][j] - dp[i-1][j-1];
            }
        }

        int x1, y1, x2, y2, result;
        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            x1 = Integer.parseInt(st.nextToken())-1;
            y1 = Integer.parseInt(st.nextToken())-1;
            x2 = Integer.parseInt(st.nextToken());
            y2 = Integer.parseInt(st.nextToken());
            result = dp[x2][y2] - dp[x1][y2] - dp[x2][y1] + dp[x1][y1];
            bw.write(result+"\n");
        }

        bw.flush(); // flush
        bw.close(); // close
        br.close(); // close
    }
}