• 欢迎光临~

# Almost Triple Deletions(CF1699D)

DP 转移时，为了保留这个数字，要保证删完后它与前一位数字相同，于是可以从前面所有与它相同的数转移过来。

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()
{
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;
for(re i = 1; i <= n; ++i)
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} ]