Untitled

mail@pastecode.io avatar
unknown
plain_text
6 months ago
3.5 kB
0
Indexable
Never
#include <bits/stdc++.h>
#define fst first
#define snd second
#define int64 long long
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, b, a) for(int i = b; i >= a; i--)

using namespace std;

typedef pair<int, int> ii;

template<class X, class Y> bool maximize(X &a, Y b)
{
    if(a >= b) return false;
    a = b;
    return true;
}

template<class X, class Y> bool minimize(X &a, Y b)
{
    if(a <= b) return false;
    a = b;
    return true;
}
const int N = 3e3 + 3, M = 4e3 + 33, MXCNT = 3e6 + 6;
int dp[N][M], a[N], val[MXCNT], id[MXCNT], b[N];

map<int, int> appear;

int cntbit = 0;

bool get_bit(int mask, int i)
{
    return (mask >> i) & 1;
}
bool check(int i, int j)
{
    int v = j - i;
    return (v != 19 && v != 8 && v != 4 && v != 5);
}
void precompute()
{
    FOR(mask, 0, (1 << 20) - 1)
    {
        bool can  = true;

        FOR(pbit, 0, 19)
        {
            if(!get_bit(mask, pbit)) continue;

            if(pbit == 0 && get_bit(mask, pbit + 19))
            {
                can = false;
            }
            if(pbit + 8 <= 19 && get_bit(mask, pbit + 8))
            {
                can = false;
            }
            if(pbit + 4 <= 19 && get_bit(mask, pbit + 4))
            {
                can = false;
            }
            if(pbit + 5 <= 19 && get_bit(mask, pbit + 5))
            {
                can = false;
            }
        }
        if(can)
        {
            cntbit++;
            id[mask] = cntbit;
            val[cntbit] = mask;
        }
    }
}
bool checkMask(int mask, int last_val, int value)
{
    FOR(bit, 0, 19)
    {
        if(get_bit(mask, bit))
        {
            int v = last_val - (19 - bit);
            if(v + 19 == value || v + 8 == value || v + 5 == value || v + 4 == value)
            {
                return false;
            }
        }
    }
    return true;
}
int main()
{
	int n;
	cin >> n;
	FOR(i, 1, n) cin >> a[i];
    sort(a + 1, a + n + 1);    
    precompute();
    
    int cnt = 0;

    FOR(i, 1, n)
    {
        appear[a[i]]++;

        if(i == 1 || a[i - 1] != a[i])
        {
            b[++cnt] = a[i];
        }
    }
    memset(dp, -0x3f, sizeof dp);

    dp[0][id[0]] = 0;
    FOR(i, 1, cnt)
    {
        if(i == 1 || b[i] - b[i - 1] > 19)
        {
            FOR(ind, 1, cntbit)
            {
                int new_mask = (1 << 19);
                maximize(dp[i][id[new_mask]], dp[i - 1][ind] + appear[b[i]]);

                maximize(dp[i][1], dp[i - 1][ind]);
                //cout << dp[1][id[new_mask]] << " " << "!!@@\n";
            }
        }
        else
        {
            FOR(ind, 1, cntbit)
            {
                int cur_bit = 0;
                int new_mask = val[ind];
                while(b[i - 1] - (19 - cur_bit) < b[i] - 19)
                {
                    new_mask /= 2;
                    cur_bit++;
                }
                new_mask |= (1 << 19);
                if(checkMask(val[ind], b[i - 1], b[i])) maximize(dp[i][id[new_mask]], dp[i - 1][ind] + appear[b[i]]);
                new_mask ^= (1 << 19);
                maximize(dp[i][id[new_mask]], dp[i - 1][ind]);
            }
        }
    }

    int res = 0;

    FOR(pos, 1, cnt)
    {
        FOR(i, 1, cntbit)
        {
            res = max(res, dp[pos][i]);
        }
    }
    cout << n - res;
}