首页 > 代码库 > History Grading

History Grading

2024-07-12 07:43:39   223人阅读

uva111:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=47

题意：看懂之后就是求两个串的最长公共子串。

题解：不过这里要注意一下，就是题目中假如说第一个数是2，表示事件1应该放在第二个位子，这样转化一下就可以了。以前集训的时候也搞过这样的东西，但是年代久远，往事早已随风而去。今天复习了一下，发现很简单的说，就是输出公共子序列的地方卡了一下。

 1 #include<iostream> 2 #include<string> 3 #include<cstring> 4 #include<cstdio> 5 using namespace std; 6 int c[100][100],b[100][100];//c[i][j]表示到a串第i位b串第j位所取得的最大长度， 7 char A[100],B[100];//b数组是用来记录的，便于DFS输出 8 int n,temp; 9 void PrintLCS(char *str1, int i, int j)  {10     if(i==0 || j==0)11         return ;12     if(b[i][j]==0){//表示原来的串中a，b是相同的13         PrintLCS(str1, i-1, j-1);14         printf("%c",str1[i-1]);15     }16     else if(b[i][j]==1)//表示a串的第i位没有取，跳过17         PrintLCS(str1, i-1, j);18     else19         PrintLCS(str1, i, j-1);//表示b串的第j位没有取，跳过20 }21 int lcs(char* A,char * B){22     int x=strlen(A);23     int y=strlen(B);24     memset(c,0,sizeof(c));25     memset(b,0,sizeof(b));26     for(int i=1;i<=x;i++){27         for(int j=1;j<=y;j++){28             if(A[i-1]==B[j-1]){29                c[i][j]=c[i-1][j-1]+1;30                b[i][j]=0;31             }32             else  if(c[i-1][j]>c[i][j-1]){//表示a串的第i位没有取，跳过33                 c[i][j]=c[i-1][j];34                 b[i][j]=1;35             }36             else{37               c[i][j]=c[i][j-1];//表示b串的第j位没有取，跳过38                 b[i][j]=-1;39             }40         }41     }42     //PrintLCS(A, x, y);43     return c[x][y];44 }45 46 int main(int argc, char const *argv[]){47 48      scanf("%d",&n);49     for(int i=1;i<=n;i++){//把数字转化成字符串50         scanf("%d",&temp);51         A[temp-1]=‘a‘+i-1;52     }53     while(~scanf("%d",&temp)){54          B[temp-1]=‘a‘;55        for(int i=2;i<=n;i++){//把数字转化成字符串56         scanf("%d",&temp);57         B[temp-1]=‘a‘+i-1;58        }59       cout<<lcs(A,B)<<endl;60     }61     return 0;62 }
View Code


联系
我们