哈理工oj 1116 解题报告 动态规划-依次输出最长公共子序列的位置-阿里云开发者社区

开发者社区> 郭大瘦> 正文

哈理工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");
    }
}

两种方法都可以

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





版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
8500 0
哈理工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  我这里有两种方法 第一种,用求最长公共子序列的方法求最长递增子序列,并用路径数组记录位置。
992 0
动态规划法——最长公共子序列问题
       这个题当初始终看不下去的原因就是当初误解了什么叫最长公共子序列,还一度以为这个题有问题,其实如果明白了什么叫最长公共子序列,也就解决了一半的问题。   什么是最长公共子序列?      什么是最长公共子序列呢?举个简单的例子吧,一个数列S,若分别是两个或多个已知序列的子序列,且是所有符合条件序列中最长的,则S称为已知序列的最长公共子序列。
1024 0
第十五章 动态规划——最长公共子序列
1、基本概念   一个给定序列的子序列就是该给定序列中去掉零个或者多个元素的序列。形式化来讲就是:给定一个序列X={x1,x2,……,xm},另外一个序列Z={z1、z2、……,zk},如果存在X的一个严格递增小标序列,使得对所有j=1,2,……k,有xij = zj,则Z是X的子序列。
787 0
阿里云服务器安全组设置内网互通的方法
虽然0.0.0.0/0使用非常方便,但是发现很多同学使用它来做内网互通,这是有安全风险的,实例有可能会在经典网络被内网IP访问到。下面介绍一下四种安全的内网互联设置方法。 购买前请先:领取阿里云幸运券,有很多优惠,可到下文中领取。
11761 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
11397 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
6567 0
+关注
郭大瘦
个人网站 oldpan.me
100
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载