哈理工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"); } }
两种方法都可以
应该还可以用栈,队列也可以得出位置,大家有谁做出来可以交流!