TYVJ1071 LCIS 线性DP+决策集优化

问题描述

TYVJ1071

题解

暴力\(\mathrm{DP}\)

首先，一个\(O(n^3)\)的解法：

设\(opt_{i,j}\)代表\(a\)的前\(i\)个和\(b\)的前\(j\)个的\(\mathrm{LCIS}\).

显然有：

1.\(a_i=b_j\)

\[opt_{i,j}=opt_{i-1,j}\]

2.\(a_i≠b_j\)

\[opt_{i,j}=max_{0 \le k < j,b_k<a_i} {opt_{i-1,k}}+1\]

于是得到代码：

#include<bits/stdc++.h>
using namespace std;

void read(int &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
    if(ch=='-') ch=getchar(),fh=-1;
    else fh=1;
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    x*=fh;
}

const int maxn=3007;

int n;
int a[maxn],b[maxn],opt[maxn][maxn];
int ans;
int main(){
    read(n);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=n;i++) read(b[i]);
//  opt[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i]!=b[j]) {opt[i][j]=opt[i-1][j];continue;}
            for(int k=0;k<j;k++) if(b[k]<a[i]) opt[i][j]=max(opt[i][j],opt[i-1][k]+1);
        }
    }
    for(int i=1;i<=n;i++) ans=max(opt[n][i],ans);
    printf("%d\n",ans);
    return 0;
}

这数据怎么这么水啊，怎么\(O(n^3)\)过\(3000\)啊。

决策集优化

发现这道题的\(\mathrm{DP}\)转移过程，已经在决策集中的决策点一定不会再出去，换而言之，这道题\(\mathrm{DP}\)的决策集是不断增大的。

于是考虑用一个变量\(val\)记录决策集中的最值，即可实现复杂度\(O(n^2)\)。

Code by lydrainbowcoat

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 3006;
int n, a[N], b[N], f[N][N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
    for (int i = 1; i <= n; i++) {
        int val = 0;
        for (int j = 1; j <= n; j++) {
            f[i][j] = (a[i] == b[j] ? val + 1 : f[i-1][j]);
            if (b[j] < a[i]) val = max(val, f[i-1][j]);
        }
    }
    int ans = 0;
    for (int j = 1; j <= n; j++) ans = max(ans, f[n][j]);
    cout << ans << endl;
    return 0;
}

总结——《算法竞赛进阶指南》

这道题的转移部分的优化告诉我们，在实现状态转移方程时，要注意观察决策集合的范围随着状态的变化情况。对于“决策集合中的预算只增多不减少”的情景，就可以像本题一样维护一个变量来记录决策集合的当前信息，避免重复扫描，把转移的复杂度降低一个量级。