提供一个代码简洁的小清新做法。

难点在于状态设计及优化。

观察数据范围，不难推断这题是 dp（当然如果赛时碰到这题肯定不会这么果断，但如果你尝试分析策略，你会一无所获）。

接下来考虑设计状态，状态一定要能正常转移，转移不了就思考少了哪些信息以至于转移不了，或是切换方向，有没有更优的 dp 主体。

以下是一些尝试，这里把状态设计表示为元组：

• $(i,j)$ 表示当前序列的第一个元素在位置 $i$，第三个在位置 $j$。选第三个可以转移到 $(i,j+1)$，但是选第一个就转移不了了，因为并不知道哪些位置是作为第三个被选的，也就不知道 $i$ 后面的数是哪一个。

• $(i,j,k)$ 表示当前序列的前三个元素分别位于 $i,j,k$，这样就能转移了，$k$ 后面是没有被取出的元素的，选第三个可以转移到 $(i,j,k+1)$。选第一个可以转移到 $(j,k,k+1)$。但是仍然有问题，此时并不知道牌堆顶部的牌具体信息，也就不清楚当前选的这张牌是否合法。

• $(i,j,k,l)$，新增了 $l$ 表示上一次决策选了原序列第 $l$ 张牌。此时选第一个会转移到 $(j,k,k+1,i)$，选第三个会转移到 $(i,j,k+1,k)$，这样就没有什么问题了，但是 $n\le 500$，而状态数是 $O(n^4)$ 的，考虑优化。

实际上有很多无效状态，直觉感受一下，可以意识到有效状态大概是 $O(n^3)$ 级别的，可以使用 map 存储状态四元组，每次取出状态拓展出新状态即可，但是由于带了个 $\log$，非常不幸地超时了。

注意到 $k=\max(j,l)+1$，那么只需要知道 $j,l$ 就能推得 $k$，也就不需要在状态里存 $k$ 了，那么就把状态数限定到了 $O(n^3)$。

代码使用记忆化搜索实现，非常简洁。

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

#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(r);i>=(l);--i)
#define pr pair<int,int>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define bg(x) (x).begin()
#define ed(x) (x).end()

#define N 505
#define int long long

int n,c[N],a[N],v[N],f[N][N][N];

inline bool jud(int i,int j){
    if(!i||!j){
        return 1;
    }
    return c[i]==c[j]||a[i]==a[j];
}

inline int dfs(int i,int j,int k,int l){
    if(~f[i][j][l]){
        return f[i][j][l];
    }

    int ans=0;

    if(i<=n&&jud(l,i)){
        ans=v[i]+dfs(j,k,k+1,i);
    }
    if(k<=n&&jud(l,k)){
        ans=max(ans,v[k]+dfs(i,j,k+1,k));
    }

    return f[i][j][l]=ans;
}

signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    memset(f,-1,sizeof f);

    cin>>n;

    rep(i,1,n){
        cin>>c[i]>>a[i]>>v[i];
    }

    cout<<dfs(1,2,3,0)<<'\n';

    return 0;
}