标题:一道求最长递增公共子序列的题,本地编译不成
取消只看楼主
青蝶
Rank: 2
等 级:论坛游民
帖 子:160
专家分:51
注 册:2018-2-4
结帖率:92%
已结贴  问题点数:20 回复次数:9 
一道求最长递增公共子序列的题,本地编译不成
题目描述:求两个整形序列的最长公共递增子序列,只需要输出其长度。其中两序列长度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
青蝶
Rank: 2
等 级:论坛游民
帖 子:160
专家分:51
注 册:2018-2-4
得分:0 
回复 2楼 lin5161678
那应该是算法不够优化,想问一下有没有更好的算法,不用开这么大的数组?
2018-06-05 20:26
青蝶
Rank: 2
等 级:论坛游民
帖 子:160
专家分:51
注 册:2018-2-4
得分:0 
回复 4楼 自学的数学
可是题目要求的数据大小是100000
2018-06-06 13:55
青蝶
Rank: 2
等 级:论坛游民
帖 子:160
专家分:51
注 册:2018-2-4
得分:0 
回复 7楼 九转星河
为什么最长公共递增子序列不一定是最长公共子序列的子集?
2018-06-06 18:25
青蝶
Rank: 2
等 级:论坛游民
帖 子:160
专家分:51
注 册:2018-2-4
得分:0 
回复 15楼 九转星河
喔~那我的算法整个都有问题
2018-06-06 18:42
青蝶
Rank: 2
等 级:论坛游民
帖 子:160
专家分:51
注 册:2018-2-4
得分:0 
在网上找了一个空间优化的代码,有些步骤没看懂,大佬们能不能帮忙解释一下?
int dp[maxn];
int a[maxn],b[maxn];
int main()
{
    int m,n;
    int i,j;
    scanf("%d %d",&m,&n);
    for(i=1;i<=m;i++)
        scanf("%d",&a[i]);
    for(i=1;i<=n;i++)
        scanf("%d",&b[i]);
    memset(dp,0,sizeof(dp));
    for(i=1;i<=m;i++)         //这个for循环里的内容没看懂
    {
        int maxx=0;
        for(j=1;j<=n;j++)
        {
            if(a[i]>b[j]) maxx=max(maxx,dp[j]);
            if(a[i]==b[j]) dp[j]=maxx+1;
        }
    }
    int ans=0;
    for(i=1;i<n;i++)
        ans=max(ans,dp[i]);
    printf("%d\n",ans);
    return 0;
}
2018-06-06 19:23
青蝶
Rank: 2
等 级:论坛游民
帖 子:160
专家分:51
注 册:2018-2-4
得分:0 
回复 18楼 九转星河
大佬能解释一下我贴的那个代码里,标注的那个for循环是什么意思么?我没看懂。
2018-06-06 20:54
青蝶
Rank: 2
等 级:论坛游民
帖 子:160
专家分:51
注 册:2018-2-4
得分:0 
这个题应该是LICS吧
2018-06-08 22:23
青蝶
Rank: 2
等 级:论坛游民
帖 子:160
专家分:51
注 册:2018-2-4
得分:0 
空间上优化了,可是时间上又超了。。总是要用到两重循环。。
2018-06-08 22:24
青蝶
Rank: 2
等 级:论坛游民
帖 子:160
专家分:51
注 册:2018-2-4
得分:0 
啊不好意思看错题了,题目要求这个子序列的数必须是后一项比前一项多1的,比如2,3,4,5,6...还不是一般的LICS
2018-06-08 23:39



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-487639-1-1.html




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

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