#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
int lcs(vector<int> v,vector<int>::iterator ind1,
                       vector<int>::iterator ind2){
   //ind2++;
   
   vector<int>::iterator it1=v.begin(),it2=v.end();
   int m=(ind2-ind1)+1,k=(it2-it1)+1;                                          
   vector< vector<int> > num;
   vector<int> vv(k,0);
   for (int i=0;i!=m;++i)
      num.push_back(vv);
   for(int i=1;i!=m;++i){
      for (int j=1;j!=k;++j){
          if (ind1[i-1]==it1[j-1])
            num[i][j]=1+num[i-1][j-1];
          else
            num[i][j]=num[i-1][j]>num[i][j-1]?num[i-1][j]:num[i][j-1];
      }
   }                                     
                                             

   return num[m-1][k-1];
}

int main(){



vector<int> vec,v;
int next,n;
cin>>n;
for (int i=0;i!=n;++i){
cin>>next;
vec.push_back(next);
}
copy(vec.begin(),vec.end(),back_inserter(v));
sort(v.begin(),v.end());
cout<<lcs(v,vec.begin(),vec.end());


system("pause");
return 0;
}

• Re:先排序再求与原列的最大公共子序列为什么会WA。。。求高手指教 (56) hehexiaobai 2010-11-27 00:53:04
  • Re:先排序再求与原列的最大公共子序列为什么会WA。。。求高手指教 (18) darkcaller 2010-12-26 14:25:32