给定一个整数序列，请问如何去掉最少的元素使得原序列变成一个全递增的序列。
输入：输入的第一行包括一个整数N(1<=N<=10000)。 接下来的一行是N个满足题目描述条件的整数。
输出：可能有多组测试数据，对于每组数据， 输出去掉最少的元素后的全递增序列。
样例输入： 8 186 186 150 200 160 130 197 220 样例输出： 150 160 197 220 提示：如果有多个结果序列满足条件，输出相对位置靠前的那个序列。
/
明显用dp，dp[j][i]表示第j个元素在第i个元素之前所能组成的最长递增子序列。
仔细思考一下，其实完全不用二维数组，只要将当前第i个元素能组成最长递增序列的值记录下来。求第j个元素的最大递增子序列时，只需将第j个元素和前j-1个元素依次比较，如果第j个元素大于第k个元素并且现在第j个元素此时最长递增子序列小于第K个元素的最长递增子序列长度加1，就更新第j个，元素所能组成的最长递增子序列的长度。
用一列数组存储每个元素最长递增子序列的前一个元素的位置，所以代码如下：
#include<iostream> #include<stdio.h> #include<algorithm> #include<string.h> using namespace std; int v[10001]; int qian[10001]; int s[10001]; int pt[10001]; int n; int main() { int j,i; while(cin>>n&&n) { for(j=0;j<n;j++) { scanf("%d",s+j); v[j]=1; qian[j]=j; } for(j=1;j<n;j++) for(i=0;i<j;i++) if(s[j]>s[i]&&v[i]+1>v[j]) { v[j]=v[i]+1; qian[j]=i; } int tp=0,ma=1; for(j=1;j<n;j++) if(v[j]>ma) { ma=v[j]; tp=j; } i=0; while(qian[tp]!=tp) { pt[i]=s[tp]; i++; tp=qian[tp]; } pt[i]=s[tp]; for(j=i;j>0;j--) printf("%d ",pt[j]); printf("%d\n",pt[0]); } return 0; } /************************************************************** Problem: 1262 User: 午夜小白龙 Language: C++ Result: Accepted Time:20 ms Memory:1676 kb ****************************************************************/
