本文共 794 字，大约阅读时间需要 2 分钟。
最长递增子序列（与最大递增子序列基本一样）
状态：dp[i]：前i个数当中，以a[i]为结尾的递增子序列的最大长度
状态转移方程跟之前写的那篇最大递增子序列的差不多
#include #include #include #define inf 100000using namespace std;int dp[1001],number[1001];struct mice //因为最后要输出老鼠的编号，因此要用结构体，保证每只老鼠的序号不会乱{ int w; int s; int num;}m[1001];bool cmp(mice x,mice y){ if(x.s!=y.s) return x.s>y.s; return x.w =0;j--) { if(m[j].w =0;i--) //找到dp[i]中最大长度的编号 if(dp[i]==max) { flag=i; break; } k=0; number[k++]=m[flag].num; //用num数组记录下对应的老鼠编号 for(i=flag;i>=0;) //逆序，找出下一个且是第一个比dp[i]小的dp[j] { first=1;temp=-inf;f=i; for(j=i-1;j>=0;j--) { if(dp[j] =0;i--) //逆序输出number数组 { printf("%d\n",number[i]); }/* for(i=0;i<=n-1;i++) printf("%d %d %d %d\n",m[i].w,m[i].s,m[i].num,m[i].head);*/ return 0;}
转载地址：http://kbdci.baihongyu.com/