题解：P11665 [JOI 2025 Final] 只不过是长的领带 2 / Just Long Neckties 2

· · 题解

非正解，纯智慧。

但前半部分的 DP 是对的。

题目限制 a_i \le 21 明示状压 DP。

但直接做还不太好，先找一下性质。

首先我们可以找到答案上界就是 \max\{a_i\}，你直接找这么多个人，一人管一种长度就行了；进一步的，我们发现除了还没有调整过的人，他们的长度一定两两不同，因为如果一个人往上调整时，如果这个长度已经有人了，那么可以直接用这个人管辖这种长度。

由于长度的不同，我们可以理解为动态插入和调整一些人满足条件，我们可以在序列上从左往右考虑，我们考虑状态 f_s，s 表示当前领带的长度集合，f_s 表示序列上能够满足条件的最长前缀，也就是在序列上最远能够走多远。

每次转移无非就两种，调整和加入一个新领带，如果是调整，则一定是贪心的将离得最近的转移过来。

然而转移过来的其实是新状态起点的位置，我们还需要知道用当前状态从 f_s 能够走到的最远位置，等价于在后面找到第一次出现连着两个元素不在集合内的位置。

先考虑 n\le 5 \times 10^5，我们可以记录 suf_{i,j,k} 表示下标 i 的后缀中第一次出现连续的 j,k 的位置，然后在 DP 转移时我们枚举补集中的两个元素 j,k，将 suf_{f_s,j,k} 取最小值即可，这样可以做到时间 O(2^{V}V^2)，空间 O(nV^2)。

其实时间是能过的，但空间爆了。

我们考虑开个 std::vector<int>[V][V] 记录下标集合，每次二分一个位置，这样时间复杂度 O(2^{V}V^2 \log n + n)，空间 O(n+2^V)，时间又太大。

容易想到压位，注意到 DP 转移时枚举了两个元素，可以看作枚举了一个元素，与整个集合的 suf 最小值，考虑将集合拆成很多段，处理每一种值对应一个集合的下标集合这样转移的时候枚举段就行了，需要自定义段长 B。

时间复杂度很神奇，是 O(n 2^B +\frac{2^V V^2 \log n}{B})，空间复杂度 O(2^V + n 2^B)，理论上 B 应该取 3 或 4 是最优的，但实际上 B 取 1 都能过。

代码如下：

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
namespace Arisa{
    inline int read(){
        int ans=0,w=1;
        char ch=getchar();
        while(ch<48||ch>57){
            if(ch=='-')w=-1;
            ch=getchar();
        }
        while(ch>=48&&ch<=57){
            ans=(ans<<1)+(ans<<3)+ch-48;
            ch=getchar();
        }
        return w*ans;
    }
    const int V=21;
    int n;
    int a[5000005];
    int f[(1<<21)+5];
    const int base=3,P=V/base+1;
    vector<int>vec[P][25][(1<<base)+5];
    void dp(){
        for(int i=1;i<(1<<V);i++)f[i]=-1e9;
        f[0]=0;
        for(int i=0;i<(1<<V);i++){
            int b=((1<<V)-1)^i;
            int minn=n;
            for(int j=0;j<V;j++){
                if(i&(1<<j))continue;
                for(int k=j/base;k<P;k++){
                    int now=(b>>(base*k))&((1<<base)-1);
                    if(!now)continue;
                    auto it=lower_bound(vec[k][j][now].begin(),vec[k][j][now].end(),f[i]+1);
                    if(it==vec[k][j][now].end())continue;
                    minn=min(minn,*it);
                    if(minn==f[i]+1)break;
                }
                if(minn==f[i]+1)break;
            }
            //其能到的位置就是 [f[i]+1,minn-1]
            f[i]=minn-1;
            int lst=-1;
            for(int j=0;j<V;j++){
                if(!(i&(1<<j))&&lst!=-1){//移位 
                    f[i^(1<<lst)|(1<<j)]=max(f[i^(1<<lst)|(1<<j)],f[i]);
                }
                if(!(i&(1<<j))){//添位 
                    f[i|(1<<j)]=max(f[i|(1<<j)],f[i]);
                }
                if(i&(1<<j))lst=j;
            }
        }
    }
    int main(){
        n=read();
        for(int i=1;i<=n;i++)a[i]=read()-1;
        for(int i=1;i<n;i++){
            int x=a[i],y=a[i+1];
            if(x>y)swap(x,y);
            int g=y/base,st=g*base;
            for(int j=0;j<(1<<base);j++)if(j&(1<<y-st))vec[g][x][j].push_back(i);
        } 
        dp();
        int minn=V;
        for(int i=0;i<(1<<V);i++)if(f[i]>=n-1){
            int cnt=0;
            for(int j=0;j<V;j++)if(i&(1<<j))++cnt;
            minn=min(minn,cnt);
        }
        cout<<minn<<'\n';
        return 0;
    }
}
int main(){
    return Arisa::main();
}
/*
1287 MB
1514 MB
10:44 subtask 123456
暂时没法做 n <= 5000000 
11:29 卡常加神秘小优化可以拿下？ 
*/