[解析アルゴリズムプール]BOJ 15724州指数

今日はDP問題を2つやりました!
最初の問題を解いた後、あまり感じが良くなくて、練習のために少し簡単な問題で解いてみましたBOJ 15724州指数、うーん、🤔 感じは見つかりましたか...私は知らないで、ほほほ、もっと練習します

BOJ 15724州指数

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

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

にゅうしゅつりょく

私の答え

DP問題なのになぜ探索のような顔をしているのか.
単純に浮かび上がる方法で、いくら解いてもO(N^2)の時間的複雑さは避けられない.(でもぜひやってみて、タイムアウトを確認してほほほ、)
DPの問題なので、入力値のすべての値にアクセスし、何かを追加して、これらの値を再利用する必要があります.そうすれば、タイムアウトを避けることができます.
この問題では、dp[i][j]には(1,1)~(i,j)の範囲内の人数の和が含まれている!でもこれはどうするのハニー.
上に、横に付けた人口とそのセルに入力した人口の数を加算して、重複する値を除外します!

i=1, j=1

(1,1)に住む人数は9人で、そのセルの前に値が入力されていないため、dp[1][1]=9となる.

i=1, j=2

(1,2)居住者数は14人で上列なし,左側に累積した人口は9人でdp[1][2]=23であった.

i=2, j=1

(2,1)居住者1人、(1,1)から累計人口9人、dp[2][1]=10.

i=2,j=2

では(2,2)居住者は31人、上下累計の人口総数は10人、23人なのでdp[2]=2]=10+23+31=64でしょうか?
Nope、そうじゃない!!
23はdp[1][1]+14、10はdp[1][1]+1である.dp[1][1]値は2回繰り返し入力!
すなわち、dp[2][2]=dp[1]+dp[2]+1]-dp[1][1](これまでの人口累計)+31((2,2)居住者)=55が正しい値である!
この方法を採用すれば、点火式はdp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + 해당 칸 인구 수完了します.
では,このように2次元dp配列を完了した後,(y 1,x 1)~(y 2,x 2)までの領域内の人口総数をどのように求めるのか.
完成したdp案では,(2,3)~(4,4)地域に住む人員を探す.

要求される領域は、淡緑色のブロックに塗られた領域の人口和であり、その値は、人口全体と黄色の領域を除く人口和以外の値である.

この領域の人口総和は、青色領域の人口総和と赤色領域の人口総和を除いた反復統計の紫色領域の人口を除く値である.

青色領域の人口合計=dp[1][4]

赤色領域の人口合計=dp[4][2]

紫色域の人口合計=dp[1][2]

はい.
結局、真京大王が2,3,4,4と叫んだら、私たちは
dp[4]-dp[1][4]-dp[4]-dp[4]+2]+dp[1][2]は、点火として表される場合に値を返す.dp[y2][x2] - dp[y2][x1] - dp[y1][x2] + dp[y1-1][x1-1]見える!!

コード#コード#

#include <iostream>
#include <vector>

// BOJ 15724 주지수, DP
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, M, T;
    cin>>N>>M;

    vector<vector<int>> dp(N+1, vector<int>(M+1, 0));

    int people;
    // dp 배열 완성 
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            cin>>people;
            dp[i][j] = people + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
        }
    }

    cin>>T;
    int y1, x1, y2, x2;
    
    for (int i = 0; i < T; ++i) {
        cin>>y1>>x1>>y2>>x2;
        // 주어진 영역의 인구 합 구하기 
        int ans = dp[y2][x2] - dp[y1-1][x2] - dp[y2][x1-1] + dp[y1-1][x1-1];
        cout<<ans<<'\n';
    }

    return 0;
}