怪盗Kidd的滑翔翼

4977:怪盗Kidd的滑翔翼

总时间范围: 
1000ms

内部存款和储蓄器约束: 
65536kB

描述
 

怪盗Kidd是二个充满神话色彩的怪盗,特地以珠宝为指标的精品盗窃犯。而她非常优异之处,就是她老是都能躲过中村警部的浩大围堵,而那也极大程度上是幸亏损她随身引导的方便操作的滑翔翼。

有一天,怪盗Kidd像未来同样偷走了黄金时代颗珍贵的钻石,不料却被柯南小伙子识破了伪装,而她的滑翔翼的重力装置也被柯南踢出的足球破坏了。不得已,怪盗Kidd只好操作受到伤害的滑翔翼逃脱。

lovebet下载 1

若果城市中总结有N幢建筑排成一条线,每幢建筑的惊人各不相符。开头时,怪盗Kidd能够在其他大器晚成幢建筑的上面。他能够选择七个样子逃跑,不过不能够中途校订方向(因为中森林警察部会在末端追击)。因为滑翔翼引力装置受到损害,他只得往下滑行(即:只好从较高的建造滑翔到异常低的修建)。他期待尽量多地因此差别建筑的最上端,那样能够缓慢下落时的冲击力,减弱受到损害的或然性。请问,他最多能够经过多少幢差异建筑的顶上部分(包罗开头时的建筑)?

 

输入
输入数据第风流罗曼蒂克行是一个整数K(K < 100),代表有K组测验数据。
每组测量试验数据包涵两行:第黄金年代行是四个整数N(N <
100卡塔尔,代表有N幢建筑。第二行李包裹涵N个不一致的整数,每贰个应和后生可畏幢建筑的中度h(0
< h < 10000),依照建筑的排列顺序给出。

输出
lovebet下载,对此每少年老成组测验数据,输出生机勃勃行,蕴含一个整数,代表怪盗Kidd最多能够经过的修造数量。

样例输入
3
8
300 207 155 299 298 170 158 65
8
65 158 170 298 299 155 207 300
10
2 1 3 4 5 6 7 8 9 10

样例输出
6
6
9

可能比较需要注意的一点,maxn要清0
代码:

 1 //*************************************
 2 //7-1   PAx: 620终端
 3 // Name: 4977 怪盗基德的滑翔翼
 4 // Solut:  D.P.
 5 //************************************
 6 #include "stdafx.h"
 7 #include <bits/stdc++.h>
 8 #define N 101
 9 int a[N], n, maxn =0 ;
10 int f1[N*N], f2[N*N];
11 using namespace std;
12 int main()
13 {
14     int t; scanf("%d", &t);
15     while (t--)
16     {
17         maxn = 0;
18         memset(a, 0, sizeof(a));
19         memset(f1, 0, sizeof(f1));
20         memset(f2, 0, sizeof(f2));
21         scanf("%d", &n);
22         for (int i = 1; i <= n; i++)
23         {
24             scanf("%d", &a[i]);
25             f1[i] = 1;
26             f2[i] = 1;
27         }
28         for (int i = 1; i <= n; i++)
29         {
30             for (int j = 1; j < i; j++)
31             {
32                 if (a[i] > a[j])
33                     f1[i] = max(f1[j] + 1, f1[i]);
34             }if (f1[i] > maxn)
35                 maxn = f1[i];
36         }
37         for (int i = n ; i >= 1; i--)
38         {
39             for (int j = n; j > i; j--)
40             {
41                 if (a[i] > a[j])
42                     f2[i] = max(f2[i], f2[j] + 1);
43             }if (f2[i] > maxn)
44                 maxn = f2[i];
45         }
46         printf("%d\n", maxn);
47     }
48     return 0;
49 }