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                 else
41                 {
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         else
51             cout << "unhappy" << endl;
52     }
53     return 0;
54 }

View Code

 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                 else
39                 {
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         else
48             cout << "unhappy" << endl;
49     }
50     return 0;
51 }

View Code

 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                 else
39                 {
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         else
48             cout << "unhappy" << endl;
49     }
50     return 0;
51 }

View Code

永远最容易理解的是消耗最大的-

today:

　　我也曾经憧憬过后来没结果

　　我也曾经做梦过后来更寂寞

　　假装我很怀旧

just follow your heart