UVA - 531 - Compromise (LCS)

题目链接：https://vjudge.net/PRoblem/UVA-531

题意：以单词为单位的LCS（Longest common subsequence）

错误代码：

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>#include <cmath>#include <vector>#include <queue>#include <stack>#include <set>#include <map>using namespace std;#define FOR(i,k,n) for(int i=k;i<n;i++)#define FORR(i,k,n) for(int i=k;i<=n;i++)#define scan(a) scanf("%d",&a)#define scann(a,b) scanf("%d%d",&a,&b)#define scannn(a,b,c) scanf("%d%d%d",&a,&b,&c)#define mst(a,n)  memset(a,n,sizeof(a))#define ll long long#define N 105#define mod 1000000007#define INF 0x3f3f3f3fconst double eps=1e-8;const double pi=acos(-1.0);char x[N][35];char y[N][35];int dp[N][N];int n,m;void solve(){    for(int i=0;i<=n;i++)        dp[i][0]=0,dp[0][i]=0;    for(int i=1;i<=n;i++)    {        for(int j=1;j<=m;j++)        {            if(strcmp(x[i],y[j])==0)                dp[i][j]=dp[i-1][j-1]+1;            else                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);        }    }}void print(int i,int j){    if(i==0 || j==0) return ;    if(dp[i][j]==dp[i-1][j-1]+1)//WA2 就算满足这个等式，x[i]也不一定和y[j]相等，即不一定是找到了LCS的成员，比如上图中i=7,j=6的时候。    {        print(i-1,j-1);        printf("%s",x[i]);        if(i==n) printf("/n");//WA1 最后一个单词不一定在LCS里面。        else printf(" ");    }    else if(dp[i][j]==dp[i-1][j])        print(i-1,j);    else        print(i,j-1);}int main(){    //freopen("in.txt","r",stdin);    //freopen("out.txt","w",stdout);    while(scanf("%s",x[1])!=EOF)    {        n=1;        while(strcmp(x[n],"#"))        {            n++;            scanf("%s",x[n]);        }        m=1;        scanf("%s",y[1]);        while(strcmp(y[m],"#"))        {            m++;            scanf("%s",y[m]);        }        n--; m--;        solve();        print(n,m);    }    return 0;}正确代码1：
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>#include <cmath>#include <vector>#include <queue>#include <stack>#include <set>#include <map>using namespace std;#define FOR(i,k,n) for(int i=k;i<n;i++)#define FORR(i,k,n) for(int i=k;i<=n;i++)#define scan(a) scanf("%d",&a)#define scann(a,b) scanf("%d%d",&a,&b)#define scannn(a,b,c) scanf("%d%d%d",&a,&b,&c)#define mst(a,n)  memset(a,n,sizeof(a))#define ll long long#define N 105#define mod 1000000007#define INF 0x3f3f3f3fconst double eps=1e-8;const double pi=acos(-1.0);char x[N][35];char y[N][35];int dp[N][N];int path[N][N];int n,m;void solve(){    mst(dp,0);    mst(path,0);    for(int i=1;i<=n;i++)    {        for(int j=1;j<=m;j++)        {            if(strcmp(x[i],y[j])==0)            {                dp[i][j]=dp[i-1][j-1]+1;                path[i][j]=1;            }            else if(dp[i-1][j]>=dp[i][j-1])            {                dp[i][j]=dp[i-1][j];                path[i][j]=2;            }            else            {                dp[i][j]=dp[i][j-1];                path[i][j]=3;            }        }    }}void print(int i,int j){    if(i==0 || j==0) return ;    if(path[i][j]==1)    {        print(i-1,j-1);        printf("%s",x[i]);        if(dp[i][j]==dp[n][m]) printf("/n");        else printf(" ");    }    else if(path[i][j]==2)        print(i-1,j);    else        print(i,j-1);}int main(){    //freopen("in.txt","r",stdin);    //freopen("out.txt","w",stdout);    while(scanf("%s",x[1])!=EOF)    {        n=1;        while(strcmp(x[n],"#"))        {            n++;            scanf("%s",x[n]);        }        m=1;        scanf("%s",y[1]);        while(strcmp(y[m],"#"))        {            m++;            scanf("%s",y[m]);        }        n--; m--;        solve();        print(n,m);    }    return 0;}
正确代码2：
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>#include <cmath>#include <vector>#include <queue>#include <stack>#include <set>#include <map>using namespace std;#define FOR(i,k,n) for(int i=k;i<n;i++)#define FORR(i,k,n) for(int i=k;i<=n;i++)#define scan(a) scanf("%d",&a)#define scann(a,b) scanf("%d%d",&a,&b)#define scannn(a,b,c) scanf("%d%d%d",&a,&b,&c)#define mst(a,n)  memset(a,n,sizeof(a))#define ll long long#define N 105#define mod 1000000007#define INF 0x3f3f3f3fconst double eps=1e-8;const double pi=acos(-1.0);char x[N][35];char y[N][35];int dp[N][N];int flag[N][N];int n,m;void solve(){    mst(dp,0);    mst(flag,0);    for(int i=1;i<=n;i++)    {        for(int j=1;j<=m;j++)        {            if(strcmp(x[i],y[j])==0)            {                dp[i][j]=dp[i-1][j-1]+1;                flag[i][j]=1;            }            else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);        }    }}void print(int i,int j){    if(i==0 || j==0) return ;    if(flag[i][j])    {        print(i-1,j-1);        printf("%s",x[i]);        if(dp[i][j]==dp[n][m]) printf("/n");        else printf(" ");    }    else if(dp[i][j]==dp[i-1][j])        print(i-1,j);    else        print(i,j-1);}int main(){    //freopen("in.txt","r",stdin);    //freopen("out.txt","w",stdout);    while(scanf("%s",x[1])!=EOF)    {        n=1;        while(strcmp(x[n],"#"))        {            n++;            scanf("%s",x[n]);        }        m=1;        scanf("%s",y[1]);        while(strcmp(y[m],"#"))        {            m++;            scanf("%s",y[m]);        }        n--; m--;        solve();        print(n,m);    }    return 0;}另外，其实用string x[N],y[N]配合cin输入，更方便。