[boj](s 1)9465シール

4191 ワード
boj テキストリンク
✅ dp ✅ Bottom Up

質問する


リンク


に答える


1.問題のアクセスと解決ロジック（解法）

  • 隣接するシールは選択できません.
  • 対角線上のシール
    • のみ選択可能
  • 単行は1つのシール
    • しか選択できません.
    定義

  • f(i,j)=i,jf(i,j)=i,jf(i,j)=i,最後にj欄を選択したときのシールスコアの最高値は
    • であった.
  • の答え
    max(f(0,n−1),f(1,n−1)),(0:i,1:j)max(f(0,n-1),f(1,n-1)),(0:i,1:j)max(f(0,n−1),f(1,n−1)),(0:i,1:j)
  • 初期値
    f(0,0)=sticker[0][0]f(0,0)=sticker[0][0]f(0,0)=sticker[0][0]
    f(0,1)=sticker[1][0]+sticker[0][1]f(0,1)=sticker[1][0]+sticker[0][1]f(0,1)=sticker[1][0]+sticker[0][1]
    f(1,0)=sticker[1][0]f(1,0)=sticker[1][0]f(1,0)=sticker[1][0]
    f(1,1)=sticker[0][0]+sticker[1][1]f(1,1)=sticker[0][0]+sticker[1][1]f(1,1)=sticker[0][0]+sticker[1][1]
  • 点火式
    f(0,j)=max(f(1,j−1),f(1,j−2))+sticker[0][j],(j>=2)f(0,j)=max(f(1,j-1),f(1,j-2))+sticker[0][j],(j>=2)f(0,j)=max(f(1,j−1),f(1,j−2))+sticker[0][j],(j>=2)
    f(1,j)=max(f(0,j−1),f(0,j−2))+sticker[1][j],(j>=2)f(1,j)=max(f(0,j-1),f(0,j-2))+sticker[1][j],(j>=2)f(1,j)=max(f(0,j−1),f(0,j−2))+sticker[1][j],(j>=2)

  • 求めた答え
    シールを外す場合は、大別して最後の行の前の行と次の行に分けられます.
    張り紙の点数が最大になるには、まずたくさん落とす必要がありますが、最後の行を落とさない理由はありません.
    したがって、シール点数の最上位値は、最後の行の前の行または次の行の両方を除いた場合に大きな値となる.

  • 初期値
    たとえば、シールが次のように表示されている場合.
    ```
50 10 100 20 40
30 50 70 10 60
```
    • f(0,0)=50f(0,0)=50f(0,0)=50
    f(0,1)=30+10=40f(0,1)=30+10=40f(0,1)=30+10=40
    f(1,0)=30f(1,0)=30f(1,0)=30
    f(1,1)=50+50=100f(1,1)=50+50=100f(1,1)=50+50=100
  • 点火式
    • (1,j−2)(1,j-2)(1,j−2)(i,j)(i,j)(i,j)(1−i,j−2)(1-i,j-2)(1−i,j−2)(1−i,j−1)(1-i,j-1)(1−i,j−1)
    (i,j)(i,j)第1のシールは、列が異なる(1,i,j)(1,i,j−2)(1,i,j)第1のシールと(1,i,j−1)(1,i,j)第1のシールに依存する.
    対角線位置のマップのみが選択可能であり、全ての行においてマップ(1−i,j)(1−i,j−1)(1−i,j−1)(1−i,j−2)(1−i,j−2)(1−i,j−2)(1−i,j−2)(1−i,j−2)(i,j)(i,j)(i,j)(i,j)を選択する条件がないからである.
    また(1,j∮2)(1,j∮2)(1,j∮1)(1,j∮i,j∮1)(1,j∮1)(1,j∮2)(1,j∮2)(1,j∮2)(1,j∮2)も含まれている.
    dp-Bottom Up(繰り返し文、Tabulation)の使用

    2.コード

    #include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>

using namespace std;

int T, n;
int sticker[2][100000];
int memo[2][100000];

int main()
{
    cin >> T;
    while(T--){
        memset(sticker, 0, sizeof(sticker));
        memset(memo, 0, sizeof(memo));

        cin >> n;
        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cin >> sticker[i][j];
            }
        }

        memo[0][0] = sticker[0][0];
        memo[0][1] = sticker[1][0] + sticker[0][1];
        memo[1][0] = sticker[1][0];
        memo[1][1] = sticker[0][0] + sticker[1][1];

        for (int j = 2; j < n; j++)
        {
            memo[0][j] = max(memo[1][j-1], memo[1][j-2]) + sticker[0][j];
            memo[1][j] = max(memo[0][j - 1], memo[0][j - 2]) + sticker[1][j];
        }

        cout << max(memo[0][n-1], memo[1][n-1]) << "\n";
    }
    
    return 0;
}

    3.時間複雑度分析


    私たちはすべての状況を見つけます.
    O(N)O(N)O(N)

    4.問題の重要な部分


    DP問題で重要なのは,点火式の導出である.
    オプションはBootm Up(繰り返し文)で展開するか、Top Down(再帰)で展開するか
    pytorchテストエラー:RuntimeError:cuda runtime error(10):invalid device ordinal at torch/csrc/cuda/Module
    2018 KAKAO BLIND RECRUITMENT秘密地図(lv 1)