题解 CF10D 【LCIS】

Plus_Ultra · 2019-09-05 22:36:57 · 题解

题解：

这道题在历经多重优化过后，终于优化到了O(N^2).

我们来看一下历经的三次思考过程:

O(N ^ 4).

我们设dp(i,j)表示第一个串考虑到第i个位置，第二个串考虑到第j个位置的LCIS长度.

我们枚举i从1~n,j从1~m.

很显然，对于A[i]≠B[j],那么dp(i,j)=0(-INF也一样).

对于A[i] = B[j],那么可以枚举 x(1~N), y(1~M),当A[x] < A[i]且B[y] < B[i]而且A[x] = B[y]时(此方案合法)，用 dp(x, y) + 1 来更新 dp(i,j).

这种方法肯定是要炸的，于是我们考虑优化.
O(N ^ 3).

通过观察可以发现，我们每次枚举x,y实际有很多情况是冗余的.

我们设dp(i,j)表示第一个串考虑到第i个位置，第二个串考虑到第j个位置,以 B[j] 为结尾的LCIS长度.

我们枚举 i 从 1~n,j 从 1~m.

很显然，对于A[i] ≠ B[j],那么dp(i,j) = dp[i-1,j].

对于A[i] = B[j],那么可以枚举 k(0~j-1) ,当B[y] < B[i]时(此方案合法)，也就是B[y] < Ai,取个max,用 dp(i-1,k) + 1 来更新dp(i,j).

这里就不多说了，感兴趣的童鞋可以分析一下代码：

int n,f[505][505],ans,m,a[505]={-1};
int b[505]={-1},p,tot,step[505][505],k,pre[505];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)  cin>>a[i];
    cin>>m;
    for(int i=1;i<=m;i++)  cin>>b[i];

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        if(b[j]==a[i]) 
        {
            for(k=0;k<j;k++)
               if(b[k]<a[i]&&f[i][j]<f[i-1][k]+1)  f[i][j]=f[i-1][k]+1,step[i][j]=k;
        }
        else  f[i][j]=f[i-1][j],step[i][j]=step[i-1][j];
    }

    for(int i=1;i<=m;i++)  
    if(f[n][i]>ans)  ans=f[n][i],p=i;

    cout<<ans<<endl;
    while(p)
    {
        pre[++tot]=b[p];
        p=step[n][p];//要找以B[J]为结尾的序列 
    }
    for(int i=tot;i>=1;i--)  cout<<pre[i]<<" ";

    return 0;
}

好了，现在我们考虑O(N ^ 2)的做法.

O(N ^ 2):

我们设 dp[i][j] 表示A前i个位置和B前j个位置所能产生的最长公共上升子序列的长度.其中强制 A[i] == B[j] ，也就是最后这个位置是匹配的.若是 A[i] != B[j] 则对应函数值为0.

我们从1到n枚举i计算dp值，在枚举i的过程中维护 f[k] = max{ dp[1~(i-1)][k] } .

然后 dp[i][j] = max { f[k] | k < j && B[k] < A[i] }，如果我们再从小到大枚举j的话只要边枚举j边记录满足条件的 f[k] 最大值即可.

总复杂度O(n * m).

下面贴一下核心代码:

还有就是在阅读lyd大佬的书之后写的程序，思想都是一样的，也可以看一下（没有路径输出，瞎搞搞就行了）：

#include <iostream>

#define N 510

using namespace std;

int n, a[N], b[N], dp[N][N], ans, m;

int main() 
{
    cin >> n;
    for (int i = 1; i <= n; i++)  cin>>a[i];
    cin >> m;
    for (int i = 1; i <= m; i++)  cin>>b[i];

    for (int i = 1; i <= n; i++) 
    {
        //两种写法

        /*int tmp = 0;
        for (int j = 1; j <= m; j++) 
        {
            dp[i][j] = (a[i] == b[j] ? tmp + 1 : dp[i-1][j]);
            if (b[j] < a[i])  tmp = max(tmp, dp[i-1][j]);
        }*/

        for (int i = 1; i <= n; i++) 
        {
            // tmp是决策集合中dp[i-1][k]的最大值
            int tmp = 0;
            // j=1时，0可以作为k的取值
            if (b[0] < a[i])  tmp = dp[i - 1][0];
            for (int j = 1; j <= m; j++) 
            {
                if (a[i] == b[j])  dp[i][j] = tmp + 1;
                else dp[i][j] = dp[i - 1][j];
                // j即将增大为j+1，检查j能否进入新的决策集合
                if (b[j] < a[i])  tmp = max(tmp, dp[i - 1][j]);
            }
        }
    }

    for (int j = 1; j <= m; j++) ans = max(ans, dp[n][j]);
    cout << ans << endl;

    return 0;
}

这不是AC的，需要输出路径，可以参考其他大佬的题解.

题解 CF10D 【LCIS】

题解：

Plus Ultra!!!