Informatics Olympiad All-in-One (1260: [Example 9.4] Intercepting Missiles (Noip1999))

1260: [Example 9.4] Intercept missile (Noip1999)

Time Limit: 1000 ms Memory Limit: 65536 KB
Commits: 15078 Passes: 5806

【Title Description】

A country has developed a missile interception system in order to defend against enemy missile attacks.But this missile interception system has a flaw: Although its first shell can reach any height, each subsequent shell cannot be higher than the previous one.One day, the radar picked up an incoming missile from an enemy country.Since the system is still in the trial phase, there is only one system, so it may not be able to intercept all missiles.

Enter the altitude of the missiles flying in sequence (the altitude data given by the radar is a positive integer not greater than 30,000, and the number of missiles is not more than 1,000), calculate this systemHow many missiles can be intercepted at most, and how many sets of such missile interception systems are required to intercept all missiles.

[Enter]

Enter the altitude at which the missiles will fly in sequence.

【Output】

The first line: the maximum number of missiles that can be intercepted;

Line 2: The minimum number of systems required to intercept all missiles.

【Sample input】

389 207 155 300 299 170 158 65

【Example of output】

62

【Analysis】

The first question is the longest non-rising subsequence.Let a[x] denote the xth element in the original sequence, and b[x] denote the length of the non-descending subsequence of length x.When processing a[x], look up the maximum length of non-descending subsequences it can be concatenated to (i.e. compare with part b[x]).Assuming that it can be connected to a non-descending subsequence with a maximum length of maxn, then b[x]=maxn+1.The maximum value that the b array is assigned to is the answer to the first question.
  The second question is the longest non-descending subsequence problem.

【Reference Code】

#include #define N 1010int dp1[N]; //The first question, the longest non-rising subsequenceint dp2[N]; //Second question, the longest sequence that does not fallint f[N]; //missile sequenceint max(int ​​x,int y){return x > y ? x : y;}int main(){int idx=0,ans=0,cnt=0;int i,j;while(scanf("%d", &f[idx])!=EOF) //Automatic end when end of file is encountered Ctrl+Eidx++;for(i=0;i

http://ybt.ssoier.cn:8088/problem_show.php?pid=1260

a>