关于算法竞赛进阶指南P267 LCIS 的问题
  • 板块学术版
  • 楼主Sola_
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/12/2 15:55
  • 上次更新2023/11/3 23:07:39
查看原帖
关于算法竞赛进阶指南P267 LCIS 的问题
373822
Sola_楼主2021/12/2 15:55

根据书中所言,朴素做法O(n^3)时转移方程的计算如下:

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

但如果面对以下数据: 4 4 2 2 1 3 2 1 2 3 则输出结果为1 但答案显然为2 将

f[i][j]=f[i-1][j]

提至

if(b[k]<b[j])

之上,并不加判断条件却可以得出正确结果 请问对于书中给出的代码是否需要做初始化以及初始化成什么 亦或是书中给出代码存在逻辑上的漏洞 萌新不解,求dalao解惑

2021/12/2 15:55
加载中...