题目大意:

找一组最长上升公共子序列,并把任意一组满足的情况输出出来

最长公共上升子序列不清楚可以先看这篇文章

http://www.cnblogs.com/CSU3901130321/p/4182618.html

然后在这基础上加回溯,我自己一开始利用两个一维数组写回溯,测了很多数据都没问题

但一直给segment fault,网上也看到有人跟我一样说不知道为什么,一维数组的代码主要函数先放在这里留待以后看能否解决,或者有大神帮忙解决

 int dp[N] , a[N] , b[N] , rec[N] , fa[N] , src[N] , maxn , cnt;

 void LCIS(int m , int n)
{
memset(dp , , sizeof(dp));
memset(src , , sizeof(src));
memset(fa , , sizeof(fa));
for(int i = ; i<=m ; i++){
int k = ;
for(int j = ; j<=n ; j++){
if(a[i] == b[j]){
if(dp[j] < dp[k] + ){
dp[j] = dp[k] + ;
src[j] = i;
fa[i] = src[k];
}
}
if(a[i] > b[j] && dp[k] < dp[j]) k = j;
}
} maxn = , cnt = ;
int s;
for(int i = ; i <= n ; i++)
{
if(maxn < dp[i])
maxn = dp[i] , s = src[i];
}
rec[cnt++] = s;
while(fa[s]){
rec[cnt++] = fa[s];
s = fa[s];
}
}

后来自己改成了二维数组来回溯

 #include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = ;
#define max(a,b) a>b?a:b
int dp[N] , a[N] , b[N] , rec[N] , maxn , cnt;
int s[N][N]; //用来回溯,记录前一次出现最大的j的位置,因为那个位置一定是会出现b[pos] = 某个a[i]的 void TraceBack(int i , int j)
{
if(i < || j < ) return ;
// cout<<"here: "<<i<<" "<<s[i][j]<<endl;
if(s[i][j] >= ){
rec[cnt++] = i; TraceBack(i- , s[i][j]);
}else TraceBack(i- , j);
} void LCIS(int m , int n)
{
memset(dp , , sizeof(dp));
memset(s , - , sizeof(s));
for(int i = ; i<=m ; i++){
int k = ;
for(int j = ; j<=n ; j++){
if(a[i] == b[j]){
if(dp[j] < dp[k] + ){
dp[j] = dp[k] + ;
s[i][j] = k;//记录上一次出现在最长子序列中能够进行匹配的j的位置
}
}
if(a[i] > b[j] && dp[k] < dp[j]) k = j;
}
} maxn = , cnt = ;
int pos ;
//我自己写的函数原因,所以必须找到第一个出现最大值的位置pos,保证在这个位置会出现某个a[i]与其匹配
/*这里从后往前找和从前往后找效果一样,但是输出的序列可能不同,
但是题目要求只输出一种情况所以也没问题,方向找,输出的正好是样例的结果
for(int i = 1 ; i<=n ; i++) 也确实AC了没问题
*/
for(int i = n ; i >= ; i--)
{
if(maxn < dp[i])
maxn = dp[i] , pos = i;
}
TraceBack(m , pos);
} int main()
{
int m , n , T;
scanf("%d" , &T);
while(T--){
scanf("%d" , &m);
for(int i = ; i<=m ; i++)
scanf("%d" , a+i); scanf("%d" , &n);
for(int i= ; i<=n ; i++)
scanf("%d" , b+i); LCIS(m , n); printf("%d\n" , maxn);
for(int i = cnt - ; i>= ; i--)
printf("%d " , a[rec[i]]);
printf("\n");
if(T>) puts("");
}
return ;
}

最新文章

  1. kafkaspot在ack机制下如何保证内存不溢
  2. 在asp.net利用jquery.MultiFile实现多文件上传(转载)
  3. $.each()
  4. WPF 获得鼠标相对于屏幕的位置,相对于控件的位置
  5. Linux匿名管道与命名管道
  6. C#泛型(二)
  7. POJ 4047 Garden 线段树 区间更新
  8. iOSbase64
  9. 小白日记12:kali渗透测试之服务扫描(二)-SMB扫描
  10. python获取本机IP、mac地址、计算机名
  11. POJ 2446 Chessboard
  12. python----iter\next
  13. CF #365 703D. Mishka and Interesting sum
  14. console.log的返回值undefined
  15. android之View绘制
  16. Analisis of Hello2 source
  17. google Kickstart Round F 2017 四道题题解
  18. js的map方法遍历数组
  19. powerdesigner 16.5 不允许有扩展属性,或对象不存在
  20. webpack配置的基本介绍

热门文章

  1. bzoj Strange Way to Express Integers【excrt】
  2. P3469 [POI2008]BLO-Blockade(Tarjan 割点)
  3. [C++ STL] 迭代器(iterator)详解
  4. [读书笔记1]《C语言嵌入式系统编程修炼》
  5. C#的装箱与拆箱与基本类型
  6. 题解报告:hdu 1061 Rightmost Digit(快速幂取模)
  7. 题解报告:hdu 5695 Gym Class(拓扑排序)
  8. tns no listener
  9. cloudera-server启动File not found : /usr/sbin/cmf-server解决办法(图文详解)
  10. Storm概念学习系列之storm的优化