## Interceptor missile

The time limit ：3000 ms  |  Memory limit ：65535 KB
difficulty ：3
Description and narration

In order to defend the enemy's missile attack . Developing a missile interception system . But there is a flaw in such a missile interception system ： Although its first shell can reach any height . But in the future, each shell can not be higher than or equal to the height of the previous one . One day . The radar caught the enemy's missiles . Because the system is still in the trial stage . So just one system . So it's possible that we can't intercept all the missiles .

Input
In the first line, enter the number of test data sets N（1<=N<=10）

The next line enters how many missiles this set of test data has in common m（1<=m<=20）

Next, enter the altitude of the missiles in turn , All height values are greater than 0 The positive integer .

Output
Output the maximum number of missiles that can be intercepted
Example input
```2
8
389 207 155 300 299 170 158 65
3
88 34 65```
Example output
```6
2```
source

[ Zhang Jiefeng ] original

Basic problems of dynamic programming , Is to find the monotonically decreasing longest subsequence , In fact, it's the same as monotonically increasing longest subsequence , Just change the inferential sentence . Thoughts are the same ;

http://blog.csdn.net/whjkm/article/details/38582411    Monotonically increasing longest subsequence can refer to the previous blog ;

Here's the code ：

```#include <cstdio>
#include <cstring>
const int maxn=25;
int a[maxn],dp[maxn],m,Max;
void LICS()
{
memset(dp,0,sizeof(dp));
for(int i=0;i<m;i++)
{
dp[i]=1;
for(int j=0;j<i;j++)
if(a[i]<a[j] && dp[i]<dp[j]+1)//a[i]<a[j] It's monotonically decreasing longest subsequence . Ideologically, it's the same as incremental
dp[i]=dp[j]+1;
}
Max=0;
for(int i=0;i<m;i++)
if(Max<dp[i])
Max=dp[i];
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
scanf("%d",&m);
for(int i=0;i<m;i++)
scanf("%d",&a[i]);
LICS();
printf("%d\n",Max);
}
return 0;
}
```

## nyist oj 79 Interceptor missile ( Basic problems of dynamic programming ） More articles about

1. nyoj 79 Interceptor missile ( Dynamic programming )

Topic link :http://acm.nyist.net/JudgeOnline/problem.php?pid=79 The meaning of the problem is to find the longest monotone decreasing subsequence #include<iostream> #inc ...

2. nyoj 79 Interceptor missile

Interceptor missile The time limit :3000 ms  |  Memory limit :65535 KB difficulty :3   describe In order to defend against the missile attack of the enemy , Developing a missile interception system . But there's a flaw in this interceptor system : Although its first shell can reach ...

3. nyoj--814-- See also interceptor missiles ( Dynamic programming + greedy )

See also interceptor missiles The time limit :3000 ms  |  Memory limit :65535 KB difficulty :3 describe You should be familiar with the subject of intercepting missiles , Let me tell you the meaning of the topic : In order to defend against the missile attack of the enemy , A new missile interception system has been developed ...

4. The longest increasing subsequence problem nyoj 17 Monotonically increasing longest subsequence nyoj 79 Interceptor missile

One ,     The description of the longest increasing subsequence problem set up L=<a1,a2,…,an> yes n A different sequence of real numbers ,L The increasing subsequence of is such a subsequence Lin=<aK1,ak2,…,akm>, among k1< ...

5. Clear orange A1120 Interceptor missile -- Dynamic programming ( Longest ascending subsequence )

Title address :http://oj.tsinsen.com/A1120 Problem description In order to defend against the missile attack of the enemy , Developing a missile interception system . But there's a flaw in this interceptor system : Although its first shell can reach any height , but ...

6. Nine degrees OJ 1197： Parity check （ Basic questions ）

The time limit :1 second Memory limit :32 mega Special questions : no Submit :3590 solve :1511 Title Description : Enter a string , Then check each character strangely , Finally output the binary number after verification ( Such as '3', Output :10110011). ...

7. Nine degrees OJ 1059：abc （ Basic questions ）

The time limit :1 second Memory limit :32 mega Special questions : no Submit :3642 solve :2869 Title Description : set up a.b.c It's all 0 To 9 Number between ,abc.bcc It's two triple digits , And there are :abc+bcc=532. Seek to satisfy the condition ...

8. Nine degrees OJ 1057： The number of （ Basic questions ）

The time limit :1 second Memory limit :32 mega Special questions : no Submit :8431 solve :2819 Title Description : Input 20 Number , Every number is in 1-10 Between , seek 1-10 The mode in ( Mode is the number that appears the most , If there is the same number of times ...

9. Nine degrees OJ 1032：ZOJ （ Basic questions ）

The time limit :1 second Memory limit :32 mega Special questions : no Submit :4569 solve :2561 Title Description : Read in a string , The string contains ZOJ Three characters , The number is not necessarily equal , Press ZOJ Sequential output , When a character runs out , The rest ...

## Random recommendation

1. Logstash The time zone 、 Time shift ,message restructuring

Applicable scenario Get the time of the log itself Log time turns Unix Time restructuring message Sample log : hellow@,@world@,@2011-11-01 18:46:43 logstash The configuration file : input{ ...

2. Delete empty folder eliminate CS Extension file bat

Delete empty folder . The deletion is clean . The deletion is thorough . Copy the following code to txt Kept in . And put the suffix .txt Destiny .bat. Then run it . programme 1.xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx ...

3. Three points --- ZOJ 3203 Light Bulb

Light Bulb Problem's Link:   http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3203 Mean: ...

4. HBase Scan Timeout-OutOfOrderScannerNextException

When migrating data recently, you need to perform a big Scan,HBase Clusters often encounter the following logs : Exception in thread "main" org.apache.hadoop.hbase.DoNot ...

5. Java Build the development environment

6. scala How to define multiple constructors

Go straight to the code : package com.test.scalaw.test.demo /** * scala Define multiple constructors , * in addition ,Scala There is only one main constructor in , The others are auxiliary constructors . And they need ...

7. 【LeetCode】Agorithms Problem set （ One ）

Single Number subject Given an array of integers, every element appears twice except for one. Find that s ...

8. Microsoft SqlSever database -- Soft strategy 1

Baidu Encyclopedia --Microsoft SqlSever SQL It's English Structured Query Language Abbreviation , It means structured query language .SQL The main function of the language is to establish links with various databases , To communicate . Press ...

9. Set off Azure AD It's the top of my head &mdash;&mdash; In depth understanding of Microsoft Graph Application and service rights declaration

author : Xi-zhang Chen Published in 2017 year 7 month 12 Japan Introduction This is an unplanned article . We all know what to do Microsoft Graph In terms of the development of , Application registration is required . I have written a special article about this before . But there is a ...

10. Applet bindtap and cachetap The difference between

<view bindtap='a'> 1 <view bindtap='b'> 2 <view bindtap='c'> 3 </view> </ ...