• 欢迎光临~

Almost Triple Deletions(CF1699D)

开发技术 开发技术 2022-10-14 次浏览

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} ]

程序员灯塔
转载请注明原文链接:Almost Triple Deletions(CF1699D)
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com