最长公共子序列O(n^2)模板

//时间复杂度O(n^2)，空间复杂度O(n^2)
 
/*
    f[][]是DP数组，0放长度，1作记录
    主要用a去扫描b，逐步优化
*/
 
#include<string.h>
#include<stdio.h>
#include<iostream.h>
 
#define MAXN 500
typedef int elem_t;
 
int GLIS(int l1, elem_t a[], int l2, elem_t b[], elem_t ans[])
{
    int f[MAXN+1][MAXN+1][2];
    int i,j,k,max;
 
    memset(f,0,sizeof(f));
    for (i=1;i<=l1;i++)
    {
        k=0;
        memcpy(f[i],f[i-1],sizeof(f[0]));
        for (j=1;j<=l2;j++)
        {
            if (b[j-1]<a[i-1] && f[i][j][0]>f[i][k][0]) k=j;
            if (b[j-1]==a[i-1] && f[i][k][0]+1>f[i][j][0])
f[i][j][0]=f[i][k][0]+1,f[i][j][1]=i*(l2+1)+k;
        }
    }
    for(max=0,i=1;i<=l2;i++)
    if (f[l1][i][0]>f[l1][max][0]) max=i;
    for(i=l1*l2+l1+max;i%(l2+1);i=f[i/(l2+1)][i%(l2+1)][1])
ans[f[i/(l2+1)][i%(l2+1)][0]-1]=b[i%(l2+1)-1];
    return f[l1][max][0];
}

本文地址：http://com.8s8s.com/it/it31602.htm