hdu1423||hdu4512--LCIS--try

要学的太多了.

学到的都是有用的即便你不会在比赛中遇到这个类型的但是开拓了你的思维

这2题都是LCIS-Longest Common Increase Subsequence

我是在这边学习的传送

这篇写的很好.

我觉得对于4512要好好理解下啊我想了好久太白痴了....注意下数组的对称性

1423：

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int size = 520;
 7 int dp[size];
 8 int ss[size] , tt[size];
 9 int n , m;    
10 
11 void LCIS( )
12 {
13     int max_len;
14     for( int i = 1 ; i<=n ; i++ )
15     {
16         max_len = 0;
17         for( int j = 1 ; j<=m ; j++ )
18         {
19             if( ss[i] > tt[j] )
20             {
21                 max_len = max( max_len , dp[j] );
22             }
23             else if( ss[i] == tt[j] )
24             {
25                 dp[j] = max_len + 1;
26             }
27         }
28     }
29 }
30 
31 int main()
32 {
33     cin.sync_with_stdio(false);
34     int t , ans;
35     cin >> t;
36     while( t-- )
37     {
38         memset( dp , 0 , sizeof(dp) );
39         cin >> n;
40         for( int i = 1 ; i<=n ; i++ )
41         {
42             cin >> ss[i];
43         }
44         cin >> m;
45         for( int i = 1 ; i<=m ; i++ )
46         {
47             cin >> tt[i];
48         }
49         LCIS( );
50         ans = 0;
51         for( int i = 1 ; i<=m ; i++ )
52         {
53             ans = max( ans , dp[i] );
54         }
55         cout << ans << endl;
56         if(t)
57             cout << endl;
58     }
59     return 0;
60 }

View Code

4512：

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int size = 210;
 7 int dp[size];
 8 int ss[size] , tt[size];
 9 int n;    
10 
11 int LCIS( )
12 {
13     int max_len , ans = 1;
14     for( int i = 1 ; i<=n ; i++ )
15     {
16         max_len = 0;
17         for( int j = 1 ; j<=n-i+1 ; j++ )
18         {
19             if( ss[i] > tt[j] )
20             {
21                 max_len = max( max_len , dp[j] );
22             }
23             else if( ss[i] == tt[j] )
24             {
25                 dp[j] = max_len + 1;
26             }
27             if( i!=n-j+1 )
28             {
29                 ans = max( ans , dp[j]*2 );
30             }
31             else
32             {
33                 ans = max( ans , dp[j]*2-1 );
34             }
35         }
36     }
37     return ans;
38 }
39 
40 int main()
41 {
42     cin.sync_with_stdio(false);
43     int t , ans;
44     cin >> t;
45     while( t-- )
46     {
47         memset( dp , 0 , sizeof(dp) );
48         cin >> n;
49         for( int i = 1 ; i<=n ; i++ )
50         {
51             cin >> ss[i];
52             tt[n+1-i] = ss[i];
53         }
54         cout << LCIS( ) << endl;
55     }
56     return 0;
57 }

View Code

today:

　　不知不觉就长到了要爱要哀愁要纠结要迟疑要理性要偷渡要分别的年龄

just follow your heart