哈理工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 

我这里有两种方法

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

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

#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");
    }
}

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