将c串从a,b串中删去后求最长公子列 直接暴会超时
#include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> using namespace std; char a[1010],b[1010],c[1010]; int dp1[1010][1010],dp2[1010][1010]; int aa[1010],bb[1010]; int main() { int t, ca = 1; scanf("%d",&t); while(t--) { scanf("%s%s%s",a,b,c); memset(dp1, 0, sizeof(dp1)); memset(dp2, 0 , sizeof(dp2)); int len1 = strlen(a), len2 = strlen(b), len3 = strlen(c); for(int i = 1; i <= len1; i++) for(int j = 1; j <= len2; j++) if(a[i-1] == b[j-1]) dp1[i][j] = dp1[i-1][j-1]+1; else dp1[i][j] = max(dp1[i-1][j], dp1[i][j-1]); for(int i = len1; i >= 1; i--) for(int j = len2; j >= 1; j--) if(a[i-1] == b[j-1]) dp2[i][j] = dp2[i+1][j+1]+1; else dp2[i][j] = max(dp2[i+1][j], dp2[i][j+1]); for(int i = 1; i <= len1; i++) { int u = 0, j; for(j = i; j <= len1; j++) { if(c[u] == a[j-1]) u++; if(u == len3) break; } if(j <= len1) aa[i] = j; else aa[i] = 0; } for(int i = 1; i <= len2; i++) { int u = 0, j; for(j = i; j <= len2; j++) { if(c[u] == b[j-1]) u++; if(u == len3) break; } if(j <= len2) bb[i] = j; else bb[i] = 0; } int _max = 0; for(int i = 1; i <= len1; i++) for(int j = 1; j <= len2; j++) if(aa[i] && bb[j]) _max = max(_max, dp1[i-1][j-1]+dp2[aa[i]+1][bb[j]+1]); printf("Case #%d: %d\n",ca++,_max+len3); } return 0; }