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

  1. 云栖社区>
  2. 博客列表>
  3. 正文

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

oldpan 2014-07-09 11:44:25 浏览86 评论0

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

两种方法都可以

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





用云栖社区APP,舒服~

【云栖快讯】诚邀你用自己的技术能力来用心回答每一个问题,通过回答传承技术知识、经验、心得,问答专家期待你加入!  详情请点击

网友评论

oldpan
文章106篇 | 关注0
关注
阿里云数据库内置的智能专家,提供云数据库问题诊断、性能优化、SQL分析、资源分析、优化报告等... 查看详情
独立的公网IP资源,可以绑定到阿里云专有网络VPC类型的ECS、NAT网关、私网负载均衡SL... 查看详情
基于全网公开发布数据、传播路径和受众群体画像,利用语义分析、情感算法和机器学习,分析公众对品... 查看详情
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
阿里云总监课正式启航

阿里云总监课正式启航