LIS（最长上升子序列）
本蒟蒻第一次写题解，请大神们多多关照
附：本此题解参考《信息学奥赛一本通》
（此题解仅为练手，方便大家的查看，其实很鸡肋）
【不耐烦地可以直接看标程，我都嫌我唠叨】
一、问题介绍
现有n个不相同的整数组成的序列，记为a[1],a[2],……，a[n]。且a[i]<>b[j](i<>j),若有一个子序列，它的下标顺序是由小到
大的（即i1<i2<i3……ie）,并且子序列中数也是由小到大排列的（即a[i1]<a[i2]<a[i3]……ie）,则这个长度为e的子序列就是
这个长度为n的序列的最长上升子序列。
例如这个长度为6的序列：18 55 21 24 63 44
它的最长上升子序列长度为4，是18 21 24 44注明：子序列和子串的区别
子串是串的一个连续的部分，而子序列是从序列中去掉任意元素而获得的新序列。也就是说，
子串的位置必须是连续的，而子序列则可以不连续二、算法分析
这道题经典的DP，我们先介绍下DP的简单思路：
动态规划有点类似递归，由后往前进行搜索（当然你也可以从前往后）
- 把一个大的问题分解成一个个的子问题，直到子问题小到不能再小，最终会得到最小子问题。最小子问题的解显而易见，这样递
推回去，就可以得到原问题的解。
我们再举栗子说这题（参考书哈，我比书更唠叨）：
1. 对于a[n]来说，它是序列的第一个数，所以当我们从后向前查找时，只存在长度为1的上升子序列。
2.我们再往前查找（则此时为a[n-1]）,则存在下面两种可能性：
(1)如果a[n-1]<b[n],则有了长度为2的上升子序列：a[n-1],a[n]。
(2)如果a[n-1]>b[n],则有了长度为1的上升子序列：a[n-1]/a[n]。
3.如果搜索到a[i],此时求最长上升子序列的方法就是：
在我们已经搜索过的数中（a[i+1],a[i+2],……,a[n]）,找出一个比b[i]大的数，将它的最长上升子序列后接在后面。
栗子：a[i]=13;a[i+1]=4;a[i+2]=23……
那我们就可以将a[i+2]所求的最长上升子序列后接在a[i]后面，假如a[i+2]所求出的最长上升子序列是23 55 103，那我
们就可将此序列接在后面，得出a[i]的最长上升子序列为13 23 55 103。三、数据结构（就是照抄书上的数据了）
为算法上的需要，定义一个整数类型的二维数组a[n][3]
1.a[i][1]表示第i个数的本值。
2.a[i][2]表示从i到n的最长上升子序列长度。
3.a[i][3]表示从i开始，最长上升子序列的下一个位置，若a[i][3]=0则后面没有连接的数。（这
个就是记录路径留后面输出的,就是伪指针）。四、样例
（n<=200）
【输入样例】
14
13 7 9 16 38 24 37 18 44 19 21 22 63 15【输出样例】
8
7 9 16 18 19 21 22 63五、上程序（看我瞎扯了多久）
- 小二~给我上书上标程
- 得嘞~~
有bug的地方一定要多多包容啊~~~
#include<bits/stdc++.h>
using namespace std;
int n,i,j,t,k,a[1000][3+1];
int main()
{
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i][1]);
a[i][2]=1;//a[i][3]定义是全局变量，自动清零
}
for(i=n-1;i>=1;i--)//n在最末尾，肯定只有长度为1的，所以这里忽略不计
{
t=0;k=0;
for(j=i+1;j<=n;j++)//寻找最长的，且能让a[i][1]接在后面的子序列
{
if((a[j][1]>a[i][1]) && (a[j][2]>t))
{
t=a[j][2]; //记录目前能让a[i][1]接在后面的子序列的最长长度
k=j;//记录下标 ，这个就是伪指针
}
}
a[i][2]=t+1;//长度加上它本身
a[i][3]=k;//记录路径
}
k=1;
for(i=1;i<=n;i++)//求最长上升子序列的起始位置
if(a[i][2]>a[k][2])
k=i;
printf("%d\n",a[k][2]);//输出最长不下降子序列长度
while(k!=0)
{
printf("%d ",a[k][1]);
k=a[k][3];
}
return 0;
}