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

    Determine your operating system version and download it JDK 1. download JDK windows System : Right click on my computer -> attribute ; Here's the picture : 2. download JDK Download address :http://www.oracle.com/index.h ...

  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> </ ...