poj 1934 Trip 所有最长公共子序列 仍然WA

发布时间:2016-12-8 6:10:01 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"poj 1934 Trip 所有最长公共子序列 仍然WA",主要涉及到poj 1934 Trip 所有最长公共子序列 仍然WA方面的内容,对于poj 1934 Trip 所有最长公共子序列 仍然WA感兴趣的同学可以参考一下。

Source Code Problem: 1934 User: csjiaxin Memory: N/A Time: N/A Language: G++ Result: Time Limit Exceeded Source Code #include <iostream> #include <stdio.h> #include<cstring> #include <set> #include <algorithm> using namespace std; #define MAX_N (80+1) #define MAX_L (1000+1) int dp[MAX_N][MAX_N]; int P[MAX_N][MAX_N]; string str1,str2; set<string> collection; //自动去重复 void doPrint(int l1,int l2,string &s) { if( l1 <= 0 || l2 <= 0) { collection.insert(s); return; } switch(P[l1][l2]) { case 1: //vc.push_front(str1[l1-1]); s.insert(s.begin(),str1[l1-1]); doPrint(l1-1,l2-1,s); //cout<<str1[l1-1]; break; case 2: doPrint(l1-1,l2,s); break; case 3: doPrint(l1,l2-1,s); break; case 4: string tmps = s; //printf("l1=%d,l2=%d\n",l1,l2); // printf("vc:\n"); // printVC(vc); // printf("tmpvc:\n"); // printVC(tmpvc); doPrint(l1-1,l2,s); doPrint(l1,l2-1,tmps); break; } } int main() { cin>>str1; cin>>str2; int l1=str1.size(),l2=str2.size(); for(int i=0;i<=l1;i++) dp[i][0]=0; for(int j=0;j<=l2;j++) dp[0][j]=0; for(int i=0;i<l1;i++) { for(int j=0;j<l2;j++) { int dp_i=i+1; int dp_j=j+1; if( str1[i] == str2[j]) { dp[dp_i][dp_j] = dp[dp_i-1][dp_j-1] +1; P[dp_i][dp_j] = 1; } else { if(dp[dp_i-1][dp_j] > dp[dp_i][dp_j-1]) { dp[dp_i][dp_j] = dp[dp_i-1][dp_j]; P[dp_i][dp_j]=2; } else if(dp[dp_i-1][dp_j] < dp[dp_i][dp_j-1]) { dp[dp_i][dp_j] = dp[dp_i][dp_j-1]; P[dp_i][dp_j] = 3; } else { dp[dp_i][dp_j] = dp[dp_i][dp_j-1]; P[dp_i][dp_j] = 4; } } } } //cout<<dp[l1][l2]<<endl; string s; doPrint(l1,l2,s); //sort(collection.begin(),collection.end()); for(set<string>::const_iterator setIter = collection.begin(); setIter != collection.end(); ++setIter) { cout<<(*setIter)<<endl; } } 第一版代码,利用递归回溯找出最长公共字符串 利用set<string>去重和排序 OLE 有时间再根据前辈文章优化

上一篇:HDU 4714 Tree2cycle 构造出一种链的方法
下一篇:bean write 标签

相关文章

相关评论