❀ 題目傳送門 ❀

https://atcoder.jp/contests/dp/tasks/dp_c

❀ 解題小技巧 ❀

這題主要的想法是第一格是位置，第二格是狀態。
dp[i][j]的意思是第 i 天時選的是 j 活動，又連續兩天不能同一個活動。
因此轉移式是這樣的：
若我選了第 1 個活動，那麼那一格就是 上一個活動選第 2 個活動 or 上一個活動選第 3 個活動 值比較大者，再加當前值。
選了第 2 個活動、第 3 個活動 也是依此類推。
最後答案就是第 n 天時 活動1、活動2、活動3 最大者。

❀ 參考程式碼 ❀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
#define burst ios::sync_with_stdio(0); cin.tie(0);

int main(){
  int dp[100005][3];
  memset(dp, 0, sizeof(dp));
  int v[100005][3];
  int n;
  cin >> n;
  for(int i = 1; i <= n; i++){
    for(int j = 0; j < 3; j++){
      cin >> v[i][j];
    }
  }
  for(int i = 1; i <= n; i++){
    dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + v[i][0];
    dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + v[i][1];
    dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + v[i][2];
  }
  cout << max({dp[n][0], dp[n][1], dp[n][2]});
}