//时间复杂度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];
}
|
本类阅读TOP10