Almost Triple Deletions(CF1699D)
考虑 DP 。设 $ dp_i $ 为强制保留这一个数，最多可以剩下几个数。
发现：当一个区间 $ [l,r] $ 满足 $ len \equiv 0 ( mod\ 2) \land 区间众数小于区间个数的一半$ 时，这个区间是可以全部删除的。
于是我们可以先 \(n^2\) 预处理每个区间是否可以全部删除，如果可以则 \(fl_{i,j}=1\) 。
DP 转移时，为了保留这个数字，要保证删完后它与前一位数字相同，于是可以从前面所有与它相同的数转移过来。
具体的：当 \((j<i) \land a_j = a_i \land (fl_{j+1,i-1}=1 \lor j=i-1)\) 时 \(dp_i=max\{dp_j+1,dp_i\}\) 。
初始化时 \(dp_1=1\) ；再求 \(fl\) 数组时，如果 \(fl_{1,i}=1\) ，\(dp_i=1\) 。
多测注意清空。
Code moo~~
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define pc_ putchar(' ')
#define pc_n putchar('\n')
#define Bessie signed
const int CTR = 5005;
int T;
int n, a[CTR];
bool fl[CTR][CTR];
int dp[CTR], tong[CTR];
int ans;
Bessie main()
{
T = read();
while(T--)
{
ans = 0;
for(re i = 1; i <= n; ++i)
dp[i] = tong[i] = 0;
for(re i = 1; i <= n; ++i)
for(re j = 1; j <= n; ++j)
fl[i][j] = 0;
n = read();
for(re i = 1; i <= n; ++i)
a[i] = read();
for(re i = 1, res; i <= n; ++i)
{
res = 0;
for(re j = i; j <= n; ++j)
{
++tong[a[j]];
if(tong[a[j]] > res)
res = tong[a[j]];
if((j - i + 1) % 2 == 0 && res <= (j - i + 1) / 2)
fl[i][j] = 1;
}
for(re j = i; j <= n; ++j)
tong[a[j]] = 0;
if(fl[1][i - 1])
dp[i] = 1;
}
dp[1] = 1;
for(re i = 2; i <= n; ++i)
{
for(re j = i - 1; j >= 1; --j)
{
if(a[j] == a[i] && (fl[j + 1][i - 1] || j == i - 1) && dp[j])
{
dp[i] = max(dp[j] + 1, dp[i]);
}
}
}
for(re i = 1; i <= n; ++i)
if(dp[i] && (fl[i + 1][n] || i == n))
ans = max(ans, dp[i]);
ot(ans),pc_n;
}
return 0;
}
\[\bm{hzoi-Creator\_157} \] 标签：Deletions,CTR,Almost,int,Triple,fl,dp,define From： https://www.cnblogs.com/Creator-157/p/16792243.html