mg4377娱乐娱城官网_mg4377娱乐手机版_www.mg4377.com

最长公共子连串,最长上升子系列

时间:2019-06-02 17:17来源:mg4377娱乐手机版
最长公共子系列,LCS,动态规划落实。 175玖:最长上升子种类 查看 提交 统计 提问 总时限:  2000ms 内部存款和储蓄器限制:  最长公共子连串,最长上升子系列。65536kB 描述 1个数的行列

最长公共子系列,LCS,动态规划落实。

175玖:最长上升子种类

  • 查看
  • 提交
  • 统计
  • 提问

总时限: 
2000ms

内部存款和储蓄器限制: 
最长公共子连串,最长上升子系列。65536kB

描述

1个数的行列bi,当b1 < b2 < ... < bS的时候,我们称那些行列是稳中有升的。对于给定的3个行列(a1a2, ..., aN),我们能够得到部分上升的子种类(ai1ai2, ..., aiK),这里1 <= i1 < i2 < ... < iK <= N。举例,对于系列(一, 7, 三, 伍, 玖, 4, ⑧),有它的部分上升子种类,如(一, 7), (叁, 肆, 8)等等。这一个子体系中最长的长短是4,比方子体系(一, 三, 伍, 八).

您的天职,就是对此给定的队列,求出最长上涨子种类的长短。

输入

输入的第二行是体系的长度N (一 <= N <= 一千)。第1行提交体系中的N个整数,这个整数的取值范围都在0到一千0。

输出

最长上涨子体系的长度。

样例输入

7
1 7 3 5 9 4 8

样例输出

4

代码:

1、

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int a[1010],f[1010],n,maxn;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i  )
    {
        scanf("%d",&a[i]);
        f[i]=1;
    }

    for(int i=2;i<=n;i  )
      for(int j=1;j<=i-1;j  )
        if(a[i]>a[j]) f[i]=max(f[j] 1,f[i]);
    for(int i=1;i<=n;i  )
      maxn=maxn>f[i]?maxn:f[i];
    printf("%d",maxn);
    return 0;
}

2、

#include<cstdio>
using namespace std;
int f[9999];
int a[9999],ans,n;
int main()
{
    f[1]=1;
    scanf("%d",&n);
    for(int i=1;i<=n;i  )
      scanf("%d",&a[i]);
    for(int i=2;i<=n;i  )
    {
        for(int j=1;j<i;j  )
          if(a[j]<a[i]&&f[j]>f[i])
            f[i]=f[j];
        f[i]  ;      
    }
    ans=f[1];
    for(int i=1;i<=n;i  )
      ans=ans>f[i]?ans:f[i];
      printf("%d",ans);
    return 0;
}

3、

#include<iostream>
using namespace std;
#include<cstdio>
const int INF=10001;
#include<cstring>
const int N=1001;
long long  a[N],c[N],f[N];
int search(int l,int r,int i)/*二分查找*/
{
    if(l==r) return l;
    int mid=(l r 1)/2;
    if(c[mid]>=a[i]) return search(l,mid-1,i);/*等号加到上面是上升序列*/
    if(c[mid]<a[i]) return search(mid,r,i);/*等号加到下面是不下降*/
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;  i)
    scanf("%d",&a[i]);
    memset(c,127,sizeof(c));
    long long int  MAX=-INF;
    for(int i=1;i<=n;  i)
    {
        f[i]=search(0,i,i) 1;
        c[f[i]]=min(c[f[i]],a[i]);
        MAX=max(f[i],MAX);
    }
    printf("%dn",MAX);
    return 0;
}

 

Java落成:最长上涨子类别LIS算法
提交二个由n个数组成的体系x[1..n],找寻它的最长单调回涨子系列。即求最大的m和a一,a贰……,am,使得a一<a贰<……<am且x[a1]<x[a2]<……<x[am]。

最长公共子连串,公共子连串

 1 /*
 2 ========最长公共子序列========
 3 所用算法 动态规划
 4 作者 程松
 5 时间 2015/12/11 16:43
 6 所用语言 c  
 7 */
 8 #include<iostream>
 9 #include<cstring>
10 #include<string>
11 using namespace std;
12 const int MAX_LENGTH = 1000;//定义字符串最大长度
13 int c[MAX_LENGTH][MAX_LENGTH];//长度为i的字符串x与长度为j的字符串的最长公共子序列长度
14 int b[MAX_LENGTH][MAX_LENGTH];//做标记
15 string x,y;
16 int x_length,y_length;
17 void init(){
18     cin>>x;
19     cin>>y;
20     x_length = x.size();
21     y_length = y.size(); 
22     c[0][0]=-1;//以下循环i,j从1开始需单独让c[0][0]为-1,最初因此原因导致错误,勿忘勿忘
23     for(int i=1;i<=x_length;  i){
24         for(int j=1;j<=y_length;  j){
25             c[i][j] = -1;//未计算过设为-1,用作备忘录
26             b[i][j] = 0;
27         }
28     }
29 }
30 int LCSLength(int i,int j,string x,string y){
31     int maxlength;
32     //记录此时的长度,做备忘录
33     if(c[i][j]!=-1){
34         maxlength = c[i][j];
35     }
36     //以下通过最优子结构求解
37     else if(i==0&&j==0){//边界条件,
38         maxlength = 0;
39     }
40     //以下为状态转移方程的实现
41     else if(x[i-1]==y[j-1]){
42         maxlength = LCSLength(i-1,j-1,x,y) 1;
43         b[i][j] = 1;
44     }else if(LCSLength(i-1,j,x,y)>=LCSLength(i,j-1,x,y)){
45         maxlength = LCSLength(i-1,j,x,y);
46         b[i][j] = 2;
47     }else{
48         maxlength = LCSLength(i,j-1,x,y);
49         b[i][j] = 3;
50     }
51     c[i][j] = maxlength;
52     return maxlength;
53 }
54 //LCS()用来求解出最长的序列并将其输出
55 void LCS(int i,int j,string x){
56     if(i==0||j==0)
57         return;
58     else if(b[i][j]==1){
59         LCS(i-1,j-1,x);
60         cout<<x[i-1];
61     }else if(b[i][j]==2){
62         LCS(i-1,j,x);
63     }else{
64         LCS(i,j-1,x);
65     }
66 }
67 int main(){
68     init();
69     cout<<LCSLength(x_length,y_length,x,y)<<endl;
70     LCS(x_length,y_length,x);
71     return 0;
72 }

 

1 /* 二========最长公共子系列======== 叁 所用算法 动态规划 四 小编 程松 5 时刻 二〇一五/12/1一 16:4三 六 所用语言 c 七 */ 8...

编辑:mg4377娱乐手机版 本文来源:最长公共子连串,最长上升子系列

关键词: 动态规划——DP 序列 算法