哈理工oj 1116 解题报告 动态规划-依次输出最长公共子序列的位置

简介: 哈理工OJ 1116 选美大赛 http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1116这道题目其实跟其他 2星 求最长递增子序列的题目没什么区别,但标记为2星半,总是有一些提升的,即是在最长递增子序列长度后面再求出子序列的位置 The number is 2: 2 3 我这里有两种方法第一种,用求最长公共子序列的方法求最长递增子序列,并用路径数组记录位置。

哈理工OJ 1116 选美大赛 http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1116


这道题目其实跟其他 2星 求最长递增子序列的题目没什么区别,但标记为2星半,总是有一些提升的,即是在最长递增子序列长度后面再求出子序列的位置 

The number is 2: 2 3 

我这里有两种方法

第一种,用求最长公共子序列的方法求最长递增子序列,并用路径数组记录位置。

画二维数组的表可以方便理解,并考虑路径数组的方向情况。

#include <cstdio>
#include <cstring>
#include <cstdlib>

#define left_up -1
#define left 1
#define up 2

int g[101];       //存放原始序列
int c[101][101];  //存放最长公共子序列数
int t;
int flag[101][101];  //标记数组

void output(int i,int j){  //输出连续递增子序列在原序列中的位置
  int po = 0;
  if(i == 0 || j == 0 || t == 0)
        return;
  if(flag[i][j] == left_up)
{
    po = 1;
    t --;
    output(i - 1,j - 1);
}
  else{
    if(flag[i][j] == up)
        output(i - 1,j);
    else
        output(i,j - 1);
  }
  if(po){
    printf("% d",j);
  }
}

int comp(const void *a,const void *b){
return *(int *)a - *(int *)b;}

void lcs(int g[],int n){  //最长公共子序列求解

   int temp[n + 1];
   for(int i = 0 ; i < n ; i ++)
      temp[i] = g[i];
    qsort(temp,n,sizeof(int),comp);
    memset(c,0,sizeof(c));
    memset(flag,0,sizeof(flag));
    for(int i = 1 ; i <= n ; i ++)
        for(int j = 1 ; j <= n ; j++){
            if( temp[i - 1] == g[j - 1] && c[i - 1][j - 1] + 1 > c[i][j - 1] && c[i - 1][j - 1] + 1 > c[i - 1][j]){ //if里的条件很重要

                c[i][j] = c[i - 1][j - 1] + 1;
                flag[i][j] = left_up;   //标记来源为左上
                }
            else{
                if(c[i][j - 1] >= c[i - 1][j]){
                    c[i][j] = c[i][j - 1];
                    flag[i][j] = left;  //标记来源为左,若左上相同,默认标记左
                }
                 else{
                    c[i][j] = c[i - 1][j];
                    flag[i][j] = up;  //标记来源为上
                 }
            }
        }
}

int main(){

  int n;
  while(scanf("%d",&n) != EOF){

      int m;
      if(n == 0)
        break;
      for(int i = 0 ; i < n ; i ++)
        scanf("%d",&g[i]);
        lcs(g,n);
        t = c[n][n];
        printf("The number is %d:",t);
        output(n,n);
        printf("\n");

  }
return 0;}


另外一种方法,是一位大神做的

利用最长递增子序列的标准方法得出最长个数,并用递归函数求出位置

#include <stdio.h>
#include<cstring>
using namespace std;
int meinv[101],dp[101];
int len=0;
int sum=0;
int dpp(int a[],int size)   //查找最大递增数的个数函数
{
    int i,j;
    for(i=1;i<=size;i++)
    {

        dp[i]=1;
        for(j=1;j<=i;j++)
        {
            if(a[i]>a[j]&&dp[j]+1>dp[i])
            {
                dp[i]=dp[j]+1;
            }
            if(sum<dp[i])
            {
                sum=dp[i];
            }
        }
    }
    return sum;
}
void out(int a[],int le)     //输出每个的编号
{                            //递归 从后到前 一次推得出 dp发生改变的序号
    int zai=0;
    if(le<0||sum==0)
        return ;
    if(dp[le]==sum)
    {
        sum--;
        zai=1;
    }
    out(a,--le);
    if(zai)
    {
        printf(" %d",le+1);
    }
}
int main()
{
    int n;
    int i,j;
    while(~scanf("%d",&n)&&n)
    {
        memset(meinv,0,sizeof(meinv));
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++)
            scanf("%d",&meinv[i]);
        printf("The number is %d:",dpp(meinv,n));
        out(meinv,n);
        printf("\n");
    }
}

两种方法都可以

应该还可以用栈,队列也可以得出位置,大家有谁做出来可以交流!





目录
相关文章
【LeetCode-每日一题】-718. 最长重复子数组
【LeetCode-每日一题】-718. 最长重复子数组
|
1月前
lanqiao OJ 246 矩阵计数
lanqiao OJ 246 矩阵计数
11 0
|
6月前
|
测试技术
最大连续子序列 (HDU - 1231)
最大连续子序列 (HDU - 1231)
|
6月前
代码随想录Day45 动态规划13 LeetCode T1143最长公共子序列 T1135 不相交的线 T53最大子数组和
代码随想录Day45 动态规划13 LeetCode T1143最长公共子序列 T1135 不相交的线 T53最大子数组和
58 0
|
6月前
|
人工智能 算法 Java
最长连续不重复子序列(蓝桥杯每日一题)
最长连续不重复子序列(蓝桥杯每日一题)
37 0
|
算法
代码随想录算法训练营第五十三天 | LeetCode 1143. 最长公共子序列、1035. 不相交的线、53. 最大子数组和
代码随想录算法训练营第五十三天 | LeetCode 1143. 最长公共子序列、1035. 不相交的线、53. 最大子数组和
58 1
|
算法
代码随想录算法训练营第五十二天 | LeetCode 300. 最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组
代码随想录算法训练营第五十二天 | LeetCode 300. 最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组
47 1
|
算法
代码随想录算法训练营第二天 | LeetCode 977.有序数组的平方、209.长度最小的子数组、59. 螺旋矩阵 II
代码随想录算法训练营第二天 | LeetCode 977.有序数组的平方、209.长度最小的子数组、59. 螺旋矩阵 II
55 0
|
算法 索引
代码随想录算法训练营第二天 |977.有序数组平方,209.长度最小的字数组,59.螺旋矩阵
代码随想录算法训练营第二天 |977.有序数组平方,209.长度最小的字数组,59.螺旋矩阵
|
Java 测试技术
hdu1231 最大连续子序列【动态规划】
hdu1231 最大连续子序列【动态规划】
36 0