| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2638 人关注过本帖
标题:一道求最长递增公共子序列的题,本地编译不成
只看楼主 加入收藏
青蝶
Rank: 2
等 级:论坛游民
帖 子:160
专家分:51
注 册:2018-2-4
结帖率:92%
收藏
已结贴  问题点数:20 回复次数:23 
一道求最长递增公共子序列的题,本地编译不成
题目描述:求两个整形序列的最长公共递增子序列,只需要输出其长度。其中两序列长度1<=n,m<=100000,每个元素大小在[1,1000000]之间,测试样例不多于1000组。

代码:
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int s1[100010],s2[100010],max_Length[100010][100010],s[100010],maxLen[100010];

int max_L(int *s,int k){         //求一维数组最大元素的下标
    int i=0,m=0;
    while(i<k){
        if(s[i]>s[m]) m=i;
        i++;
    }
    return m;
}

int main(void){
  int T,n,m,i,j,k;
  cin>>T;
  while(T--){                                    //先求出最长公共子序列,再求其中递增元素的个数
    cin>>n>>m;
    for(i=0;i<n;i++) cin>>s1[i];
    for(j=0;j<m;j++) cin>>s2[i];
    for(i=0;i<=n;i++) max_Length[i][0]=0;
    for(j=0;j<=m;j++) max_Length[0][j]=0;
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            if(s1[i-1]==s2[j-1]) max_Length[i][j]=max_Length[i-1][j-1]+1;
            else max_Length[i][j]=max(max_Length[i-1][j],max_Length[i][j-1]);
        }
    }                                                                            //模板题,求出最长公共子序列元素个数
    for(i=0,j=1;j<=m;j++){
        if(max_Length[n][j]>max_Length[n][j-1]) s[i++]=s2[j-1];                  //求出最长公共子序列,存到数组s里面
    }
    k=i;                       
    for(i=0;i<k;i++) maxLen[i]=1;                                             //模板题,求出最长递增子序列的元素个数
    for(i=1;i<k;i++){
        for(j=0;j<i;j++){
            if(maxLen[i]>maxLen[j]) maxLen[i]=max(maxLen[i],maxLen[j]+1);
        }
    }
    cout<<max_L(maxLen,k);
}
   return 0;
}

编译的时候显示:
C:\Users\Lenovo\AppData\Local\Temp\ccA7g89Q.s    Assembler messages:
278        C:\Users\Lenovo\AppData\Local\Temp\ccA7g89Q.s    Error: value of 0000000950b5dcb2 too large for field of 4 bytes at 0000000000000372
294        C:\Users\Lenovo\AppData\Local\Temp\ccA7g89Q.s    Error: value of 0000000950bbf7a8 too large for field of 4 bytes at 00000000000003a8
310        C:\Users\Lenovo\AppData\Local\Temp\ccA7g89Q.s    Error: value of 0000000950bbf7e7 too large for field of 4 bytes at 00000000000003e7
315        C:\Users\Lenovo\AppData\Local\Temp\ccA7g89Q.s    Error: value of 0000000950bbf7fe too large for field of 4 bytes at 00000000000003fe
322        C:\Users\Lenovo\AppData\Local\Temp\ccA7g89Q.s    Error: value of 0000000950bbf819 too large for field of 4 bytes at 0000000000000419

求帮忙看下怎么回事?

        
搜索更多相关主题的帖子: 最长 子序列 int i++ for 
2018-06-05 18:03
lin5161678
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:45
帖 子:1136
专家分:3729
注 册:2011-12-3
收藏
得分:4 
int s1[100010],s2[100010],max_Length[100010][100010],s[100010],maxLen[100010];
太大

https://zh.
2018-06-05 19:54
青蝶
Rank: 2
等 级:论坛游民
帖 子:160
专家分:51
注 册:2018-2-4
收藏
得分:0 
回复 2楼 lin5161678
那应该是算法不够优化,想问一下有没有更好的算法,不用开这么大的数组?
2018-06-05 20:26
自学的数学
Rank: 13Rank: 13Rank: 13Rank: 13
等 级:贵宾
威 望:46
帖 子:967
专家分:4146
注 册:2017-11-15
收藏
得分:4 
如果改成这样就可以了:
int s1[10010],s2[10010],max_Length[10010][10010],s[10010],maxLen[10010];
2018-06-06 09:24
青蝶
Rank: 2
等 级:论坛游民
帖 子:160
专家分:51
注 册:2018-2-4
收藏
得分:0 
回复 4楼 自学的数学
可是题目要求的数据大小是100000
2018-06-06 13:55
自学的数学
Rank: 13Rank: 13Rank: 13Rank: 13
等 级:贵宾
威 望:46
帖 子:967
专家分:4146
注 册:2017-11-15
收藏
得分:0 
由于这数据太大以至于编译都无法通过,目前是这样的吗?
2018-06-06 14:43
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:4 
用树链表示最长公共子序列,然后还要再用类似的方法求出最长递增子序列~
100000数据规模o(n^2)或者会超时,或者试试找一种o(n*log(n))的求最长公共子序列的方法~
记得有种算法专门求最长公共子序列的,具体可以去搜搜(我忘记那个算法名称了)~
嗯,这题我也不能保证我能弄出来,我,还是先放下了,或者到时看看谁弄出来了可以来参考一下

PS:还有,最长公共递增子序列必然是最长公共子序列的子集么,这个不一定是吧,还是感觉要用树链表示最长公共子序列~

[此贴子已经被作者于2018-6-6 15:20编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-06-06 15:17
lin5161678
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:45
帖 子:1136
专家分:3729
注 册:2011-12-3
收藏
得分:0 
算法没看
内存空间不够用就上 malloc 吧
先把编译错误处理了

https://zh.
2018-06-06 16:28
自学的数学
Rank: 13Rank: 13Rank: 13Rank: 13
等 级:贵宾
威 望:46
帖 子:967
专家分:4146
注 册:2017-11-15
收藏
得分:0 
编译错误好处理,只要:
using namespace std;
double s1[10010],s2[10010],max_Length[10010][10010],s[10010],maxLen[10010];

double max_L(double *s,int k){         //求一维数组最大元素的下标
    int i=0,m=0;
    while(i<k){
        if(s[i]>s[m]) m=i;
        i++;
    }
    return m;
}就可以了,但是其他的。。。。。。至少这样可以运行。
2018-06-06 16:41
lin5161678
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:45
帖 子:1136
专家分:3729
注 册:2011-12-3
收藏
得分:0 
回复 9楼 自学的数学
你这样会数组越界的

https://zh.
2018-06-06 16:48
快速回复:一道求最长递增公共子序列的题,本地编译不成
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.039682 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved