http://acm.

#include <iostream>
#include <string>
int maxa[1000];
using namespace std;
void solve()
{
    string a,b;
    cin>>a>>b;
    int lena=a.size(),lenb=b.size(),cnt=0,ans=0,i,j,tmp;
    for (i=0;i<lena;i++)
    {
        tmp =0;
        for (j=0;j<lenb;j++)
        {
            if (a[i] == b[j])
            {
                if (tmp <maxa[j])
                    tmp = maxa[j];
            }
        }
        maxa[i]=tmp+1;
        cout<<maxa[i]<<endl;
    }
    int max=0;
    for(i=0;i<lena;i++)
        if (max<maxa[i])
            max=maxa[i];
        cout<<max<<endl;
}
int main()
{
    int n;
    cin>>n;
    while (n--)
        solve();
    return 0;
}

[ 本帖最后由 love24114 于 2012-2-5 19:21 编辑 ]

1.我真没看懂你的代码在干什么。
2.你的输出格式就不满足题目要求，它只要输出最长公共子序列的长度。cout<<maxa[i]<<endl;是多余的输出，或许只是你测试时加进入的。

最长公共子序列是一个经典问题，应用动态规划法解。
这段代码是最基础的解法，为方便没做空间上的优化。AC

#include<stdio.h>
#include<string.h>

int c[1001][1001];

int LCS(char * sa, char * sb)
{
    int i, j, la, lb;
    la = strlen(sa);
    lb = strlen(sb);
    for(i = 1; i <= la; i++)
    for(j = 1; j <= lb; j++)
    c[i][j] = (sa[i - 1] == sb[j - 1]) ? c[i - 1][j - 1] + 1 : (c[i - 1][j] >= c[i][j - 1]) ? c[i - 1][j] : c[i][j - 1];//个人喜好，如果还没有熟练掌握这类语法基础请勿模仿
    return c[la][lb];
}

int main()
{
    int n;
    char sa[1001], sb[1001];
    for(scanf("%d", &n); n--;)
    {
        scanf("%s%s", sa, sb);
        printf("%d\n", LCS(sa, sb));
    }
    return 0;
}

动态规划啊……
scanf("%s%s", sa, sb);为什么看到这个我忍不住要笑。

呵呵，不要笑，严肃点。那是两个很有意义的变量名。

下午和朋友去K歌了，十一点多才回来。明天上午八点半还要开个会，就不和你们闲聊了

其实这题只要用1000的一维数组就可以了  因为每一个dp[i][j]只由dp[i-1][j-1] dp[i-1][j] dp[i][j-1]转移过来

所以没必要保存所有的结果  详见北航的http://www.   题目只给80K内存

老杨说的没错。昨天太晚了，随手写的。而且南阳理工的内存限制很宽松。