P11665 题解

· · 题解

题意

给定序列 a，选出一个子序列 b，满足 a 中每两个相邻元素至少有一个被选入 b，求 b 最长下降子序列长度的最小值。

引理

Dilworth 定理：对于任意有限偏序集，其最长链中元素的数目必等于其最小反链划分中反链的数目，简称“最长链等于最小反链覆盖”。

那么，b 最长下降子序列的长度，就等于，最少用多少个不降子序列能覆盖整个 b 序列。

思路

考虑如何求最小反链覆盖，可以贪心地做，维护目前所有已用的不降序列，当新加入元素 a_i 时，选择结尾元素最大的合法序列接上 a_i，若都不合法则新开一个序列。

因为我们只关心不降序列的结尾，而且不会出现相同结尾，所以可以用 2^a 状压表示每个不降序列。

记 f_{i,s} 为考虑前 i 个元素，b 选中第 i 个元素，目前不降序列情况是 s 的可行性，容易做到 O(n2^a)。

但这还不够优，所以我们尝试将可行性 DP 变为数值 DP。

发现我们只关心 f_{n-1,s}|f_{n,s} 是否为 1，或者说我们关心的是对于某个状态 s，满足 f_{i,s} 为 1 的最大 i，不妨记为 g_s。

每次暴力跳然后更新别的状态即可，时间复杂度不会证，貌似可以势能分析（？），反正我自己没卡掉。

#include <iostream>
#include <cstdio>
using namespace std;
int n,m,k,a[5000001],p[2097152],f[2097152],ans=1000000000;
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i) {
        scanf("%d",&a[i]);
        m=max(m,a[i]);
    }
    k=1<<m;
    for(int i=0;i<k;++i) {
        p[i]=p[i>>1]+(i&1);
        while(f[i]<n-1&&(i>>a[f[i]+1]-1&1|i>>a[f[i]+2]-1&1)) ++f[i];
        if(f[i]>=n-1) ans=min(ans,p[i]);
        for(int j=0;j<m;++j) {
            int x=i|1<<j;
            if(x==i) continue;
            if(j&&(x>>j-1&1)) x^=1<<j-1; 
            f[x]=max(f[x],f[i]);
        }
    }
    printf("%d",ans);
    return 0;
}