最长上升子序列

· · 个人记录

\Huge \mathsf {最长上升子序列} \Large \color{blue}{ {\Bbb{First.} \mathsf{朴素求法}} }

设 dp_i 表示以 i 结尾的最长上升子序列长度，很显然转移方程为：

dp_i = \max _{i - 1}^{j = 1} dp_j + 1[a_j < a_i]

边界条件 ： 初始每个上升子序列列中仅有一个元素，即为它他自己，所以 dp_i = 1。

for (int i = 1; i <= n; i ++) dp[i] = 1;
for (int i = 1; i <= n; i ++){
    for (int j = 1; j < i; j ++){
        if(a[i] > a[j]) dp[i] = max(dp[i], dp[j] + 1);
    }
}
\Large \color{blue}{ {\Bbb{Second.} \mathsf{二分}} }

设 sma_i 为长度为 i 的上升子序列的最小结尾值。

显然，sma 满足单调上升。

证明：

反证法： 若 sma_j \le sma_i [i < j] 则 sma_j 的前驱一定比 sma_i 小，则 sma_i 与 sma_i 为最小值矛盾，遂结论成立。

所以，我们每加入一个元素 x，使用二分查找 sma 中第一个大于等于 x 的值， 若不存在， 则以其结尾的上升子序列为目前最长的上升子序列， 使 len + 1，将 sma_{len} 设为 x， 否则 sma_{pos} = x

for (int i = 1; i <= n; i ++){
    int pos = lowerbound(sma + 1, sma + 1 + len, a[i]) - sma;
    if(pos == 0) sma[++ len] = a[i];
    else sma[pos] = a[i];
}
\Large \color{blue}{ {\Bbb{Third.} \mathsf{树状数组}} }

从朴素做法来看， 第二层循环本质上是在查找 0 \sim a_i - 1 中最大的 dp 值， 可以在值域上建立树状数组， 用 O(n \log n) 的时间复杂度

来实现朴素做法中的第二层循环的作用，简单粗暴。

for (int i = 1; i <= n; i ++){
    dp[i] = getmax(a[i] - 1) + 1;
    modify(a[i], dp[i]);
}

变式

1. 计数

朴素做法

先求 dp 数组， 每次扫一遍，统计所有满足 dp_j = dp_i - 1 的方案数，再将所有 dp_i 等于 ans 的 cal_i 加起来即可。

边界：cal_i = 1

for(int i = 1;i <= n;i ++){
    for(int j = 0;j < i;j ++){
        if(a[i] > a[j] && dp[i] == dp[j] + 1) cal[i] = (cal[i] + cal[j]) % mod;
    }
    if(dp[i] == ans1) ans2 = (ans2 + cal[i]) % mod;
}

二分

统计 sma_i 的更新历史的 cal_i 和即可。

int n, len;
ll ans;
int a[M], dp[M], g[M];//g 二分中的辅助数组，表示所有长度为 i 的上升子序列中尾部元素的最小值
// dp 表示以 i 结尾的最长上升子序列长度
ll cal[M];// cal 表示以 i 结尾的最长上升子序列个数
vector<ll> his[M], sum[M];//his 更新历史, sum his 中的 cal[his[i][j]] 的前缀和数组
int getsum(int x) {
    int le = dp[x] - 1;
    int l = 0, r = his[le].size() - 1;
    if (r < 0) return 1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (his[le][mid] >= a[x]) l = mid + 1;
        else r = mid;
    }
    return (sum[le].back() - (l ? sum[le][l - 1] : 0) + mod) % mod;
}

signed main() {
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> a[i], g[i] = INF;
    for (int i = 1; i <= n; i ++) {
        int l = 1, r = len;
        while (l < r) {
            int mid = (l + r) / 2;
            if (g[mid] >= a[i]) r = mid;
            else l = mid + 1;
        }
        if (a[i] > g[len]) {
            g[++ len] = a[i];
            dp[i] = len;
            cal[i] = getsum(i) % mod;
            his[len].push_back(a[i]), sum[len].push_back(cal[i]);
        } else {
            dp[i] = l;
            cal[i] = getsum(i) % mod;
            if (a[i] < g[l]) {
                his[l].push_back(a[i]);
                ll ps = (sum[l].back() + cal[i]) % mod;
                sum[l].push_back(ps);
            }
            g[l] = min(g[l], a[i]);
        }
    }
    for (int i = 1; i <= n; i ++) if (dp[i] == len) ans = (ans + cal[i]) % mod;
    cout << len << ' ' << ans << endl;
    return 0;
}

树状数组（不理解

int n, ans, sum, a[M];
int f[M], ca[M]; //树状数组
int dp[M], cal[M];//答案数组
int lowbit(int x){return x & (-x);}
void getans(int x, int &a, int &b){
    int ma = 0, cnt = 1;
    for(int i = x; i;i -= lowbit(i)){
        if(f[i] > ma)
            cnt = ca[i];    
        else if(f[i] == ma)
            cnt =  (cnt + ca[i]) % mod;
        ma = max(f[i], ma);
    }
    a = ma + 1, b = cnt;
}
void modify(int x, int a, int b){
    for(int i = x;i <= n;i += lowbit(i)){
        if(f[i] < a) ca[i] = b;
        else if(f[i] == a) ca[i] = (ca[i] + b) % mod;
        f[i] = max(f[i], a);
    }
}
signed main() {
    IOS;
    cin >> n;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    for(int i = 1;i <= n;i ++){
        getans(a[i] - 1, dp[i], cal[i]);
        if(dp[i] > ans) ans = dp[i], sum = cal[i];
        else if(dp[i] == ans) sum = (sum + cal[i]) % mod;
        modify(a[i], dp[i], cal[i]);
    }
    cout << ans << ' ' << sum << endl;
    return 0;
}

字典序最小

类比最长公共子序列求最小字典序方案。判断每个字符能否加入最长上升子序列，注意需要离散化。

int n, len;
int a[M];
int dp[M];
int first[M];

signed main() {
    IOS;
    cin >> n;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    for(int i = n;i >= 1;i --){
        dp[i] = 1;
        for(int j = i + 1;j <= n;j ++) if(a[i] < a[j]) dp[i] = max(dp[i], dp[j] + 1);
        len = max(len, dp[i]);
    }
    cout << len << endl;
    for(int i = 1;i <= n;i ++) if(!first[a[i]]) first[a[i]] = i;
    int up = 0, now = 0;
    for(int i = len; i; i --){
        for(int j = n;j > up;j --){
            int f = first[j];
            if(dp[f] == i && f > now){
                cout << j << ' ';
                up = j, now = f;
                break;
            }
        }
    }
    return 0;
}