最长上升子序列

Acwing895 最长上升子序列

for(int i = 1; i <= n; i++) f[i] = 1; // 初始化
for(int i = 1; i <= n; i++)
    for(int j = 1; j < i; j++)
        if(a[j] < a[i])
            f[i] = max(f[i],f[j]+1);
int ans = 0;
for(int i = 1; i <= n; i++) ans = max(ans,f[i]); // 遍历找最大值

最长上升子序列 nlogn

Acwing896 最长上升子序列2

int ans = 1;
f[ans] = a[1];
for(int i = 2; i <= n; i++) 
    if(a[i] > f[ans]) f[++ans] = a[i];
    else *(lower_bound(f+1,f+ans+1,a[i])) = a[i];
// ans 即为答案

导弹拦截

Acwing1010 拦截导弹
P1020 导弹拦截

// 最长不上升自序列
// lower_bound upper_bound 默认数组为升序

int ans = 1;
f[ans] = a[1];
for(int i = 2; i <= n; i++)
    if(a[i] >= f[ans]) f[++ans] = a[i];
    else *(upper_bound(f+1,f+ans+1,greater<int>())) = a[i];
// ans 即为答案
// 用upper_bound因为可以相等
// 序列的不上升子序列最少划分数等于序列的最长上升子序列长度

最长公共子序列

Acwing897 最长公共子序列

// f[i][j] 表示串A的前i个与串B前j个中的最长公共子序列

for(int i = 1; i <= n; i++) 
    for(int j = 1; j <= m; j++)
        f[i][j] = max(f[i-1][j-1]+(a[i] == b[j] ? 1 : 0), max(f[i-1][j],f[i][j-1]));

最长上升公共子序列 (鸽)

Acwing272 最长公共上升子序列

// f[i][j] 表示串A的前i个数字，串B的前j个数字中以b[j]结尾的最长公共上升子序列

for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= n; j++) {
        f[i][j] = f[i-1][j];
        if(a[i] == b[j])
            for(int k = 1; k < j; k++)
                if(b[k] < b[j])
                    f[i][j] = max(f[i][j],f[i-1][j-1]+1);
    }
}

// 优化

for(int i = 1; i <= n; i++) {
    int val = 0;
    for(int j =  1; j <= n; j++) {
        f[i][j] = f[i-1][j];
        if(a[i] == b[j]) {
            f[i][j] = max(f[i][j],val+1);
        }
        if(b[j] < a[i]) val = max(va,)
    }
}