Codeforces Round ＃804 (Div. 2) D. Almost Triple Deletions time limit per test2 seconds (dp好题)

题目传送门

题目大意

给定一个长度为n的数组,其中可以通过一个操作使得相邻的两个不同的数移除序列，求经过任意次操作后，最终该序列最大能有多少个相同的数剩余。

题目思路

赛场上拿到这道题，想到了以下几点：
对于一段序列，只有当该段序列中出现最多次数的数的次数小于整体一半，那么该段数便可以消去。
于是赛场上便开始对这道题开始疯狂贪心。
在快结束时，想到$n^2$可以去枚举i,j之间的消去性然后转移，到此比赛也结束了。
赛后看了大佬的代码，确实，就是将以上两点结合起来，就可以dp了。
为了判断1，我们只需要在第二重dp时，倒着扫,然后记录最大出现次数即可。
由此而看该题的模型还是十分简单的。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
#define int long long
int a[104][104];
int jc[maxn];
void solve()
{
    
    int n;
    cin>>n;
    vector<int>dp(n+2,-maxn);
    dp[0]=0;
    vector<int>a(n+3);
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n+1;i++)
    {
    
        vector<int>vis(n+1);
        int mx=0;
        for(int j=i-1;j>=0;j--)
        {
    
            if((a[i]==a[j]||i==n+1||j==0)&&(i-j)%2==1&&mx*2<=i-j-1)dp[i]=max(dp[j]+1,dp[i]);
            mx=max(mx,++vis[a[j]]);
        }
        //cout<<i<<" "<<dp[i]<<'\n';
    }
    cout<<dp[n+1]-1<<'\n';
}
signed main()
{
    
	ios::sync_with_stdio(false);
	int t = 1;
	cin >> t;
	while (t--)solve();
	return 0;
}