A93768 正经题解

分析题意
每天有三种活动，每种活动都有一定的价值，相邻两天不能选相同，求最大价值。
解题思路
先看总问题，最大价值就是最后一天的最大价值，它可以表示为在最后一天选择了某样活动的最优解，即选择活动的价值加上前一天非相同活动的最优解，而前一天的活动又可表示为……
最终，归回第一天，第一天没有前一天，因此选择每种活动的最大价值是固定的。通过这个固定值，我们就可以一步步推出最优解。
AC代码

#include <bits/stdc++.h>
using namespace std;
long long a[100005], b[100005], c[100005], dp[100005][3];

int main(){
    int n;
    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];
    }
    long long ans = 0;
    cout << *max_element(dp[n], dp[n]+3);
    
    return 0;
}

滚动数组优化

#include <bits/stdc++.h>
using namespace std;
long long a[100005], b[100005], c[100005], dp[2][3];

int main(){
    int n;
    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[0][0] = dp[1][0], dp[0][1] = dp[1][1], dp[0][2] = dp[1][2];
        dp[1][0] = max(dp[0][1], dp[0][2])+a[i];
        dp[1][1] = max(dp[0][0], dp[0][2])+b[i];
        dp[1][2] = max(dp[0][0], dp[0][1])+c[i];
    }
    cout << *max_element(dp[1], dp[1]+3);
    
    return 0;
}

时间复杂度
$O(n)$。