题意：看懂之后就是求两个串的最长公共子串。
题解：不过这里要注意一下，就是题目中假如说第一个数是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 else 19 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 }