首页 > 代码库 > hdu--4681--dp
hdu--4681--dp
这个dp应该算lcs加上一些模拟处理吧
lcs我们大家都会求 很简单。
这边的话 就是先算出 a b两个字符串从前往后 与 从后往前的lcs
因为 我们在算d的长度的时候 是向两边进行拓展的。
然后 拿c分别于a和b去暴力匹配 分别找出以a b中的字符串中的每个位置起始点 可以包含c这个字符串的子序列的最左边位置
这边 一定是最左边的 这样就会尽可能地留出多余位置 去和另一个字符串进行 lcs 这样就是使拓展长度可能地增加。
这题 我在work函数 那边花了超长时间 很容易出错= = 。。
1 #include <iostream> 2 #include <cstring> 3 #include <vector> 4 #include <utility> 5 #include <algorithm> 6 using namespace std; 7 8 const int size = 1010; 9 char a[size] , b[size] , c[size]; 10 int preDp[size][size] , nextDp[size][size]; 11 int lenA , lenB , lenC; 12 vector< pair<int,int> > va , vb; 13 14 void preLcs( ) 15 { 16 for( int i = 1 ; i<=lenA ; i++ ) 17 { 18 for( int j = 1 ; j<=lenB ; j++ ) 19 { 20 if( a[i]==b[j] ) 21 preDp[i][j] = preDp[i-1][j-1] + 1; 22 else 23 preDp[i][j] = max( preDp[i][j-1] , preDp[i-1][j] ); 24 } 25 } 26 } 27 28 void nextLcs( ) 29 { 30 for( int i = lenA ; i>=1 ; i-- ) 31 { 32 for( int j = lenB ; j>=1 ; j-- ) 33 { 34 if( a[i]==b[j] ) 35 nextDp[i][j] = nextDp[i+1][j+1] + 1; 36 else 37 nextDp[i][j] = max( nextDp[i][j+1] , nextDp[i+1][j] ); 38 } 39 } 40 } 41 42 void solve( char* str , int num , vector< pair<int,int> >& ve ) 43 { 44 int cnt , i , k; 45 if( lenC==1 ) 46 { 47 for( i = 0 ; i<num ; i++ ) 48 { 49 if( str[i]==c[1] ) 50 { 51 ve.push_back( make_pair(i+1,i+1) ); 52 } 53 } 54 } 55 else 56 { 57 for( i = 0 ; i<num ; i++ ) 58 { 59 cnt = 1; 60 if( str[i]==c[cnt] ) 61 { 62 ++ cnt; 63 for( k = i+1 ; k<num ; k++ ) 64 { 65 if( str[k]==c[cnt] ) 66 { 67 ++ cnt; 68 } 69 if( cnt==lenC+1 ) 70 { 71 ve.push_back( make_pair(i+1,k+1) ); 72 break; 73 } 74 } 75 } 76 } 77 } 78 } 79 80 int work( ) 81 { 82 int vAsize = va.size(); 83 int vBsize = vb.size(); 84 int ans = 0; 85 for( int i = 0 ; i<vAsize ; i++ ) 86 { 87 88 for( int j = 0 ; j<vBsize ; j++ ) 89 { 90 ans = max( ans , preDp[ va[i].first-1 ][ vb[j].first-1 ]+nextDp[ va[i].second+1 ][ vb[j].second+1 ]+lenC ); 91 } 92 } 93 return ans; 94 } 95 96 int main() 97 { 98 cin.sync_with_stdio(false); 99 int t;100 cin >> t;101 for( int k = 1 ; k<=t ; k++ )102 {103 cin >> (a+1) >> (b+1) >> (c+1);104 lenA = strlen( a+1 );105 lenB = strlen( b+1 );106 lenC = strlen( c+1 );107 memset( preDp , 0 , sizeof(preDp) );108 memset( nextDp , 0 , sizeof(nextDp) );109 va.clear();110 vb.clear();111 preLcs( );112 nextLcs( );113 solve( (a+1) , lenA , va );114 solve( (b+1) , lenB , vb );115 cout << "Case #" << k << ": " << work() << endl;116 }117 return 0;118 }
hdu--4681--dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。