先将暴力转移方程列出来：设 \(dp_{i,j,k,l}\) 表示当前 A 牌堆最上面三张分别是第 \(i,j,k\) 张牌，B 牌堆最上面是第 \(l\) 张的最大价值。则有：
\[dp_{i,j,k,l}\to dp_{j,k,k+1,i}(c_i=c_l\lor a_i=a_l)
\]
\[dp_{i,j,k,l}\to dp_{i,j,k+1,k}(c_k=c_l\lor a_k=a_l)
\]
\(O(n^4)\)，明显不能过。考虑优化。发现状态数 \(O(n^4)\)，转移 \(O(1)\)，优化状态即可。
容易发现，两种转移的目标装态的 \(k\) 都为 \(k+1\)。可以考虑优化这一维。同时发现，要么 \(k=j+1\)，要么 \(k=l+1\)。所以可以将状态变为 \(dp_{i,j,k,0/1}\) 表示 A 牌堆最上面三张为第 \(i,j,j+1/l+1\) 张牌，B 牌堆最上面为第 \(k\) 张的最大值。一样转移即可。
对于处理最后 \(j,k\) 可能为 \(0\) 或 \(>n\) 的情况，可以先塞两个全为 \(0\) 的物品到最后。
code：
点击查看代码
int n,m,a[N],b[N],c[N],dp[N][N][N][2];
void Yorushika(){
scanf("%d",&n);
rep(i,1,n){
scanf("%d%d%d",&a[i],&b[i],&c[i]);
}
n++,a[n]=b[n]=c[n]=0;
n++,a[n]=b[n]=c[n]=0;
mems(dp,-0x3f);
dp[2][3][1][0]=c[1];
dp[1][2][3][1]=c[3];
int ans=0;
rep(i,1,n){
rep(j,1,n){
rep(l,1,n){
if(dp[i][j][l][0]>-1e9){
int k=j+1;
if(a[i]==a[l]||b[i]==b[l]||!a[i])
dp[j][k][i][0]=max(dp[j][k][i][0],dp[i][j][l][0]+c[i]);
if(a[k]==a[l]||b[k]==b[l]||!a[k])
dp[i][j][k][1]=max(dp[i][j][k][1],dp[i][j][l][0]+c[k]);
ans=max(ans,dp[i][j][l][0]);
}
if(dp[i][j][l][1]>-1e9){
int k=l+1;
if(a[i]==a[l]||b[i]==b[l]||!a[i])
dp[j][k][i][0]=max(dp[j][k][i][0],dp[i][j][l][1]+c[i]);
if(a[k]==a[l]||b[k]==b[l]||!a[k])
dp[i][j][k][1]=max(dp[i][j][k][1],dp[i][j][l][1]+c[k]);
ans=max(ans,dp[i][j][l][1]);
}
}
}
}
printf("%d\n",ans);
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)
Yorushika();
}