【DP经典】noi openjudge 2.6 最长上升子序列

题目：

1759:最长上升子序列

总时间限制:  2000ms   内存限制:  65536kB

描述 一个数的序列b_i，当b₁ < b₂ < ... < b_S的时候，我们称这个序列是上升的。对于给定的一个序列(a₁, a₂, ..., a_N)，我们可以得到一些上升的子序列(a_i1, a_i2, ..., a_iK)，这里1 <= i₁ < i₂ < ... < i_K <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8). 你的任务，就是对于给定的序列，求出最长上升子序列的长度。 输入 输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。 输出 最长上升子序列的长度。 样例输入 7 1 7 3 5 9 4 8 样例输出 4

分析：

题目的要求其实就是在保证上升的情况下串尽可能长，输出长度

那么就可以用数组b[i][1]表示数值，b[i][2]表示从下标为i到序列末的最长长度

从末尾开始循环，i=n,n-1....1;j=i+1,i+2...n;也就是寻找一个b[j][1]>b[i][1]并且b[j][2]是从i往后最大的

最后，找到最大的b[i][2]输出

代码如下：

#include<cstdio> int b[1003][3],i,j,l,k,n;//b[i][1]:数值 b[i][2]:从i到n的最长序列长度 int main() { scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&b[i][1]); b[i][2]=1;b[i][3]=0; } for(i=n-1;i>=1;i--) { l=k=0; for(j=i+1;j<=n;j++) if(b[j][1]>b[i][1]&&b[j][2]>l) l=b[j][2]; if(l>0) b[i][2]=l+1; } k=1; for(j=1;j<=n;j++) if(b[j][2]>b[k][2]) k=j; printf("%d",b[k][2]); }