首页 > 代码库 > hdu4545--暴力/水dp--LCS/LIS真的是个好东西
hdu4545--暴力/水dp--LCS/LIS真的是个好东西
数据不大 可以暴力做..
不想提这该死的暴力了 晓爷 你出来 保证不打死你！
这题 也可以用Lcs来做 相比于以往的最裸的lcs 就是多了个 hash配对
只要多添加个条件就可以了
既然是Lcs 那么就可以用 滚动数组来优化下
因为dp[i][j] 这一状态 只与dp[i-1][j] dp[i-1][j-1] dp[i][j-1]这3个状态有关 那么即只和这一行和前一行有关系 我们可以只开一个2维数组 第一维的大小为2就足够了 存储当前行与上一行的值 以后就不断转移 覆盖
还可以更节约内存 只通过2个中间变量 来传递状态的值
var----dp[i-1][j-1] dp[j-1] ----- dp[i][j-1] dp[j] ----- dp[i-1][j]
暴力的代码 不贴了 搞的心好累.
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 const int size = 1010; 7 char ss[size]; 8 char tt[size]; 9 int dp[size];10 bool hash[30][30];11 12 int main()13 {14 int t , m , len1 , len2 , var , temp;15 char x , y;16 cin >> t;17 for( int k = 1 ; k<=t ; k++ )18 {19 cin >> (ss+1) >> (tt+1);20 cin >> m;21 memset( dp , 0 , sizeof(dp) );22 memset( hash , false , sizeof(hash) );23 len1 = strlen(ss+1);24 len2 = strlen(tt+1);25 while( m-- )26 {27 cin >> x >> y;28 hash[x-‘a‘][y-‘a‘] = true;29 }30 for( int i = 1 ; i<=len1 ; i++ )31 {32 var = 0;33 for( int j = 1 ; j<=len2 ; j++ )34 {35 temp = dp[j];36 if( ss[i] == tt[j] || hash[ tt[j]-‘a‘ ][ ss[i]-‘a‘ ] )37 {38 dp[j] = var + 1;39 }40 else41 {42 dp[j] = max( dp[j-1] , dp[j] );43 }44 var = temp;45 }46 }47 cout << "Case #" << k << ": ";48 if( dp[len2] == len1 )49 cout << "happy" << endl;50 else51 cout << "unhappy" << endl;52 }53 return 0;54 }
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 const int size = 1010; 7 char ss[size]; 8 char tt[size]; 9 int dp[size][size];10 bool hash[30][30];11 12 int main()13 {14 int t , m , len1 , len2;15 char x , y;16 cin >> t;17 for( int k = 1 ; k<=t ; k++ )18 {19 cin >> (ss+1) >> (tt+1);20 cin >> m;21 memset( dp , 0 , sizeof(dp) );22 memset( hash , false , sizeof(hash) );23 len1 = strlen(ss+1);24 len2 = strlen(tt+1);25 while( m-- )26 {27 cin >> x >> y;28 hash[x-‘a‘][y-‘a‘] = true;29 }30 for( int i = 1 ; i<=len1 ; i++ )31 {32 for( int j = 1 ; j<=len2 ; j++ )33 {34 if( ss[i] == tt[j] || hash[ tt[j]-‘a‘ ][ ss[i]-‘a‘ ] )35 {36 dp[i][j] = dp[i-1][j-1] + 1;37 }38 else39 {40 dp[i][j] = max( dp[i-1][j] , dp[i][j-1] );41 }42 }43 }44 cout << "Case #" << k << ": ";45 if( dp[len1][len2] == len1 )46 cout << "happy" << endl;47 else48 cout << "unhappy" << endl;49 }50 return 0;51 }
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 const int size = 1010; 7 char ss[size]; 8 char tt[size]; 9 int dp[2][size];10 bool hash[30][30];11 12 int main()13 {14 int t , m , len1 , len2;15 char x , y;16 cin >> t;17 for( int k = 1 ; k<=t ; k++ )18 {19 cin >> (ss+1) >> (tt+1);20 cin >> m;21 memset( dp , 0 , sizeof(dp) );22 memset( hash , false , sizeof(hash) );23 len1 = strlen(ss+1);24 len2 = strlen(tt+1);25 while( m-- )26 {27 cin >> x >> y;28 hash[x-‘a‘][y-‘a‘] = true;29 }30 for( int i = 1 ; i<=len1 ; i++ )31 {32 for( int j = 1 ; j<=len2 ; j++ )33 {34 if( ss[i] == tt[j] || hash[ tt[j]-‘a‘ ][ ss[i]-‘a‘ ] )35 {36 dp[i%2][j] = dp[(i-1)%2][j-1] + 1;37 }38 else39 {40 dp[i%2][j] = max( dp[(i-1)%2][j] , dp[i%2][j-1] );41 }42 }43 }44 cout << "Case #" << k << ": ";45 if( dp[len1%2][len2] == len1 )46 cout << "happy" << endl;47 else48 cout << "unhappy" << endl;49 }50 return 0;51 }
永远 最容易理解的 是 消耗最大的-
today:
我也曾经憧憬过 后来没结果
我也曾经做梦过 后来更寂寞
假装我很怀旧
hdu4545--暴力/水dp--LCS/LIS真的是个好东西
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。