- 题目描述：
-
给定一个整数序列，请问如何去掉最少的元素使得原序列变成一个全递增的序列。
- 输入：
-
输入的第一行包括一个整数N(1<=N<=10000)。
接下来的一行是N个满足题目描述条件的整数。
- 输出：
-
可能有多组测试数据，对于每组数据，
输出去掉最少的元素后的全递增序列。
- 样例输入：
-
8 186 186 150 200 160 130 197 220
- 样例输出：
-
150 160 197 220
- 提示：
-
如果有多个结果序列满足条件，输出相对位置靠前的那个序列。
代码如下:
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <algorithm> 5 #define finf -999999999 6 7 int n; 8 int num[10002]; 9 int cnt[10002]; 10 int last[10002]; 11 12 void show(int n) { 13 if(n == -1) { 14 return; 15 } 16 show(last[n]); 17 printf("%d ",num[n]); 18 } 19 int main(int argc, char const *argv[]) 20 { 21 while(scanf("%d",&n) != EOF) { 22 for(int i = 0; i < n; i++) { 23 scanf("%d",&num[i]); 24 last[i] = -1; 25 } 26 cnt[0] = 1; 27 for(int i = 1; i < n; i++) { 28 bool isFind = false; 29 int maxf = finf; 30 int maxj = -1; 31 for(int j = i-1; j >= 0; j--) { 32 if(num[j] < num[i]) { 33 int temp = cnt[j]+1; 34 isFind = true; 35 if(maxf <= temp) { 36 maxf = temp; 37 maxj = j; 38 } 39 } 40 } 41 if(!isFind) { 42 cnt[i] = 1; 43 last[i] = -1; 44 } 45 else { 46 cnt[i] = maxf; 47 last[i] = maxj; 48 } 49 } 50 int max = finf; 51 int maxi = -1; 52 for(int i = 0; i < n; i++) { 53 //printf("%d ",cnt[i]); 54 if(max < cnt[i]) { 55 max = cnt[i]; 56 maxi = i; 57 } 58 } 59 60 show(last[maxi]); 61 printf("%d ",num[maxi]); 62 } 63 return 0; 64 }
第一次提交错误，因为没有输出位置靠前的序列，把35行的<改成<=后通过