[普及]93768题解

题目大意

过于简单，不在累赘，请自行理解

思路

考虑 dp。

设 $dp_{i,j}$为第 $i$ 天选择活动 $j$ 时的最大总愉悦值，其中 $j \in \{0 , 1 ,2\}$ 分别对应活动 $A,B,C$。同时由于不能连续两次选择一样的活动，即 $dp_{i - 1,j}$ 与 $dp_{i , j}$ 无关联。
稍加思考后，我们得出，对于$i \ge 2$时的转移方程：

$$dp_{i , 0} = \max(dp_{i-1,1} + B_i , dp_{i - 1 , 2} + C_i)$$

$$dp_{i , 1} = \max(dp_{i-1,0} + A_i , dp_{i - 1 , 2} + C_i)$$

$$dp_{i , 2} = \max(dp_{i-1,0} + A_i , dp_{i - 1 , 1} + B_i)$$

初始状态：

$$dp_{1 , 0} = A_1 ,dp_{1 , 1} = B_1,dp_{3, 0} = C_1$$

最后输出 $3$ 中情况里的最大值即可（即最后一天分别选择活动 A,B,C）

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
#define int long long
int dp[N][3] , a[N] , b[N] , c[N] , n;//其中0表示本天选A，1表示选B，2表示选C 
signed main(){
	cin >> n;
	for(int i = 1;i <= n;i ++) cin >> a[i] >> b[i] >> c[i];
	dp[1][0] = a[1] , dp[1][1] = b[1] , dp[1][2] = c[1];
	for(int i = 2;i <= n;i ++){//动态转移方程
		dp[i][0] = max(dp[i - 1][1] , dp[i - 1][2]) + a[i];
		dp[i][1] = max(dp[i - 1][0] , dp[i - 1][2]) + b[i];
		dp[i][2] = max(dp[i - 1][0] , dp[i - 1][1]) + c[i];
	}
	cout << max({dp[n][0] , dp[n][1] , dp[n][2]});
	return 0;
}

当然，可以进行滚动数组优化/使用递推以做到更好性能。但是会导致代码可读性降低，因此不给出代码。（实际是上不想写）