競プロ日記#25/04/09

アルゴ式-Ex. ハッシュテーブル

• 正直難しすぎた。
• 解説を読んで実装の流れというか概念みたいなものは理解できたのだが実装内容がよくわからなかった（おそらくこれはC++の言語仕様を最低限しか理解できてないせい。文法が理解できていない）
• また、解説を読んで実装の流れがわかっただけで1から実装できるかといわれるとそこまでの理解は足りていない。要復習

アルゴ式-表と数値 (2)

• 表と数値 (1)の要領でやれば大きな問題なく実装できる。

アルゴ式-3 つの仕事

• 結局DP特有の以下のような考え方が重要

1. i 日目に仕事 0 を行う場合：dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + A[i][0]
2. i 日目に仕事 1 を行う場合：dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + A[i][1]
3. i 日目に仕事 2 を行う場合：dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + A[i][2]

// 1, 2, ..., N-1 日目の報酬を求める
for (int i = 1; i < N; ++i) {
   dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + A[i][0];
   dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + A[i][1];
   dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + A[i][2];
}

• そしてこれらの状態を管理するdp[][]配列の管理が重要。
  0,1,2いずれの仕事からスタートした場合の軌跡がdp[][]で管理されていること

// 動的計画法の配列を用意する
   vector<vector<int>> dp(N, vector<int>(3, 0));