首页 > 代码库 > hdu1423||hdu4512--LCIS--try
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 }
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 else32 {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 }
today:
不知不觉就长到了要爱要哀愁要纠结要迟疑要理性要偷渡要分别的年龄
hdu1423||hdu4512--LCIS--try
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。