考虑 $dp$

我们需要设置 $dp$ 数组，$dp_{i,j}$：表示小 H 刷题在第 $i$ 天，在第 $j$ 个平台刷题后获得的最大的快乐值。

所以我们的 $j\in(0,1,2)$ 分别代表这三个平台。

注意初始值：$dp_{0,j}=0,j\in(0,1,2)$

那么状态转移方程就是：

$$dp_{i,j_1}=\max(dp_{i-1,j_2}, dp_{i-1,j_3}) + w_{i,j_1} \\ dp_{i,j_2}=\max(dp_{i-1,j_1}, dp_{i-1,j_3}) + w_{i,j_2} \\ dp_{i,j_3}=\max(dp_{i-1,j_1}, dp_{i-1,j_2}) + w_{i,j_3} \\ $$

$w_{i,j}$ 表示第 $i$ 天在平台 $j$ 上刷题获得的快乐值。

时间复杂度 $O(n)$

#include <bits/stdc++.h>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;

void solve() {
	int n;
	std::cin >> n;
	std::vector dp(n + 1, std::vector<i64>(3));
	std::vector<int> Z(n + 1), P(n + 1), C(n + 1);
	for (int i = 1; i <= n; i++) {
		std::cin >> Z[i] >> P[i] >> C[i];
	}
	dp[1][0] = Z[1];
	dp[1][1] = P[1];
	dp[1][2] = C[1];
	for (int i = 2; i <= n; i++) {
		dp[i][0] = std::max(dp[i - 1][1], dp[i - 1][2]) + Z[i];
		dp[i][1] = std::max(dp[i - 1][0], dp[i - 1][2]) + P[i];
		dp[i][2] = std::max(dp[i - 1][0], dp[i - 1][1]) + C[i];
	}

	std::cout << std::max({dp[n][0], dp[n][1], dp[n][2]}) << '\n';
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int t; 
	std::cin >> t;
	while (t --) {
		solve();
	}

	return 0;
}