以下这份暴力代码是一份常数巨小、可以过掉 $35$ 分的 $O(n^4)$ 考场代码，尽管这个唐诗没有发现第四层循环是 $i\sim j$ 的，可以优化到 $O(n^3)$。

思路：设 $f_{i,j,0/1}$ 表示考虑到第 $i$ 位，其中上一个与 $a_i$ 不同色的数字为 $a_j$，$a_i$ 的颜色为红色或蓝色（$0$ 或 $1$，好像这个也可以省掉）。

$f_{i,j,x}$ 可以由 $f_{j,k,!x}$ 转移，其中 $i>j>k$。

于是得到了如下代码，可是它 WA on #6，仅仅得了 $30$ 分：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T;
int n,a[2005];
int col[2005];
int dp[2005][2005][2];
int dfs(int x){
	if(x==n+1){
		int ans=0;
		for(int i=1;i<=n;i++){
			for(int j=i-1;j;j--){
				if(col[i]==col[j]){
					if(a[i]==a[j])ans+=a[j];
					break;
				}
			}
		}
		//cout<<"ans - "<<ans<<endl;
		return ans;
	}
	int ans=0;
	col[x]=1;
	ans=max(ans,dfs(x+1));
	col[x]=2;
	ans=max(ans,dfs(x+1));
	return ans;
}
int ans;
signed main(){
	//freopen("color.in","r",stdin);
	//freopen("color.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n;i++)cin>>a[i];
		if(n<=15){
			cout<<dfs(1)<<'\n';
		}
		else{
			memset(dp,0,sizeof(dp));
			ans=0;
			
			for(int i=1;i<=n;i++){
				for(int j=0;j<i;j++){
					for(int k=0;k<j;k++){
						int f1=dp[j][k][1],f2=dp[j][k][0];
						if(a[k]==a[j+1])f1+=a[k],f2+=a[k];
						for(int l=j+1;l<i;l++){
							if(a[l]==a[l+1])f1+=a[l],f2+=a[l];
						}
						dp[i][j][0]=max(dp[i][j][0],f1);
						dp[i][j][1]=max(dp[i][j][1],f2);
					}
				}
			}
			for(int i=0;i<n;i++){
				ans=max(ans,max(dp[n][i][0],dp[n][i][1]));
			}
			cout<<ans<<endl;
		}
	}
	return 0;
}

为什么会挂掉一个点