EDPC

基本的なDPの復習をしました

今日は基本的なDPの復習をしました。

以前（約半年前）に初めてけんちょんさんの記事で勉強したときには、DPについて理解は進みましたが、まだ配るDPと貰うDPの違いもはっきりしていませんでした。

今では両者の違いをしっかり理解できています。

qiita.com

Flog 1

atcoder.jp

EDPCのAのFlog1を書いてみて、配るDPの方がしっくりくるなと感じました。

類題の柱柱柱（Flogとほぼ同一問題）
C - 柱柱柱柱柱
が緑dif（試験管901）ですが、今ではもっと低くなっているのではないでしょうか。

Vacation

atcoder.jp

夏休みに虫取り、海水浴、宿題を日替わりでする問題です。
宿題やって幸福度があがる子どもは幸せです。

Vacation もこのレベルなら自力で余裕で書けます。

#include <bits/stdc++.h>
using namespace std;

int main(){
  
  //入力
  int N;
  cin>>N;
  int a[N];
  int b[N];
  int c[N];   
  for(int i=0;i<N;i++){
    cin>>a[i]>>b[i]>>c[i];
  }
  
  //dpテーブルを0で初期化
  int dp[N][3];
  for(int i=0;i<N;i++){
    for(int j=0;j<3;j++){
      dp[i][j]=0;
    }
  }
  
  //dp
  
  dp[0][0]=a[0];
  dp[0][1]=b[0];
  dp[0][2]=c[0];
  
  for(int i=1;i<N;i++){
    dp[i][0]=dp[i-1][1]+a[i];
    dp[i][0]=max(dp[i][0],dp[i-1][2]+a[i]);
    dp[i][1]=dp[i-1][0]+b[i];
    dp[i][1]=max(dp[i][1],dp[i-1][2]+b[i]);    
    dp[i][2]=dp[i-1][0]+c[i];
    dp[i][2]=max(dp[i][2],dp[i-1][1]+c[i]); 
  }
  cout<<max(max(dp[N-1][0],dp[N-1][1]),dp[N-1][2])<<endl;
  return 0;
}
 

ただし、けんちょんさんの模範回答とくらべるとあまり美しくありません。

    // ループ
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 3; ++k) {
                if (j == k) continue;
                chmax(dp[i + 1][k], dp[i][j] + a[i][k]);
            }
        }
    }

さらにがんばります

DPは非常に応用範囲が広くいろいろなパターンがあります。
まだナップサックをすらすら書けるか自信がありません。

さらにがんばります。