*crossed matching

//  看了半天题目，总感觉跟那个最长公共子序列有某种联系，所以慢慢写，慢慢想，暴搜呗，没想到也一次ac了，但是时间好像 //　 有点长，没关系啦，想我这种弱菜，能a就很不错了，还强调神马时限之类的，不过我总感觉我写的程序很多事靠运气a了，希望 //　 一些路过的读者能指出错误... 1 Source Code 2  3 Problem: 1692        User: eth1 4 Memory: 4500K        Time: 360MS 5 Language: C++        Result: Accepted 6 Source Code 7 #include <iostream> 8 #include <algorithm> 9 #include <cstring>10 using namespace std;11 int a[1000],b[1000],f[1000][1000],map[1000][1000];12 int main()13 {14     int t;15     cin>>t;16     while(t--)17     {18         int n,m;19         cin>>n>>m;20         for(int i=1;i<=n;i++) {cin>>a[i];f[i][1]=0;}21         for(int j=1;j<=m;j++) {cin>>b[j];f[1][j]=0;}22         memset(map,0,sizeof(map));23         for(int i=1;i<=n;i++)24         {25             for(int j=1;j<=m;j++)26             {27                 if(a[i]==b[j])28                 map[i][j]=a[i];29             }30         }31 32         for(int i=2;i<=n;i++)33         {34             for(int j=2;j<=m;j++)35             {36                 f[i][j]=f[i-1][j];37                 for(int k=j-1;k>=1;k--)38                 {39                     if(map[i][k])40                     {41                         for(int c=i-1;c>=1;c--)42                         {43                             //if(map[])44                             for(int d=j;d>k;d--)45                             {46                                 if(map[c][d] && map[c][d]!=map[i][k])47                                 {48                                     //if(k)49                                     f[i][j]=max(f[i][j],f[c-1][k-1]+1);50                                 }51                             }52                         }53                     }54                 }55             }56         }57         cout<<f[n][m]*2<<endl;58     }59     return 0;60 }

原文链接: https://www.cnblogs.com/eth0/archive/2011/05/13/2045886.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍