多个串的最长公共子序列

从一个给定的串中删去（不一定连续地删去）0个或0个以上的字符，剩下地字符按原来顺序组成的串。例如：“ ”，“a”，“xb”，“aaa”，“bbb”，“xabb”，“xaaabbb”都是串“xaaabbb”的子序列。（例子中的串不包含引号。）

编程求N个非空串的最长公共子序列的长度。限制：$2<=N<=100$；N个串中的字符只会是数字0，1，…，9或小写英文字母a，b，…，z；每个串非空且最多含100个字符；N个串的长度的乘积不会超过$30000$。

输入格式:

文件第1行是一个整数T，表示测试数据的个数（1<=T<=10）。接下来有T组测试数据。各组测试数据的第1行是一个整数Ni，表示第i组数据中串的个数。各组测试数据的第2到N+1行中，每行一个串，串中不会有空格，但行首和行末可能有空格，这些空格当然不算作串的一部分。

输出格式:

输出T行，每行一个数，第i行的数表示第i组测试数据中Ni个非空串的最长公共子序列的长度。

输入样例:

1
3
ab
bc
cd

输出样例：

0

题解：和两个的思路是一样的，因为这里有n个串，所以，我们假设开n维数组，转移方程和两个串的是一样的，但是因为这里你不知道几维数组，所以，我们可以将n维转化为已知的维数，我们看到最后，有一个条件就是各个字符串的长度乘积不超过30000，所以，这很明显是想让我们用乘积来表示。

但是，假设只有乘积的时候会有一个问题，就是3 * 4 和 2 * 6表示不同的状态，但是他们的乘积是一样的，所以这样的话dp[x]表示的状态不是唯一的，转移方程的时候会出现错误。

所以我们思考怎么才能让他表示的状态唯一，我们可以想到用类似于哈希的过程，就是将他们转化为类似于进制的过程。

我们假设当前第i个串处于第j位，那么k*len[i]+j就是当前的状态值，这样就可以保证唯一性，因为他是一个递乘的过程，所以可以在一定程度上保证唯一性（至少这个题应该够用，主要是每个串的长度不一定，所以可能会产生冲突，具体实现看代码）

下面解决另一个问题，就是他有n维，我们也不知道他有几维，这个问题就很简单了，很明显的递归，用了递归，我们就不用知道他的维数了。

下面是AC代码：

#include
#include
#include
#include
char s[200][200];
int len[200];
int dp[40000];
int n;
int f(int x[])
{
    int a,b,i,j,t;
    for(i=1; i<=n; i++)
    {
        if(x[i]==0)
        {
            return 0;
        }
    }
    //寻找当前的状态
    for(a=x[n]-1,i=n-1; i>=1; i--)
    {
        a=a*len[i]+x[i]-1;//类似于进制转化，消除冲突的过程
    }
    if(dp[a]>=0)//记忆化搜索
    {
        return dp[a];
    }
    //查看当前串的值是不是相等
    for(i=2; i<=n; i++)
    {
        if(s[1][x[1]-1]!=s[i][x[i]-1])
        {
            break;
        }
    }
    //相等的话就是dp[i-1][j-1]+1这个过程
    if(i>n)
    {
        for(j=1; j<=n; j++)
        {
            x[j]--;
        }
        b=f(x)+1;
        for(j=1; j<=n; j++)
        {
            x[j]++;
        }
    }
    //不相等就是dp[i][j]=max(dp[i-1][j],dp[i][j-1])这个过程
    else
    {
        b=0;
        for(j=1; j<=n; j++)
        {
            x[j]--;
            t=f(x);
            b=max(t,b);
            x[j]++;
        }
    }
    dp[a]=b;
    return b;
}

int main()
{
    int t,i;
    int m[200];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=1; i<=n; i++)
        {
            scanf("%s",s[i]);
            len[i]=strlen(s[i]);//固定长度
            m[i]=strlen(s[i]);//每个串的位置
        }
        memset(dp,-1,sizeof(dp));
        printf("%d\n",f(m));
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

整体的思路还是很简单的，就是实现起来比较麻烦。

这个空间复杂度的证明我感觉可以仿照进制的证明，感觉应该不会超过40000的，也可以开的稍微大一点

至于这个冲突呢，只能说是可能解决了大多数冲突，我没有找出能够反驳的例子。