Question 1 [1322: [example 6.4] interceptor missile problem (noip 1999)]
[Title Description]
In order to defend against the missile attack of the enemy country, a certain country has developed a missile interception system, but this interception system has a defect: although its first shell can reach any height, each shell in the future cannot be higher than the height of the previous one. One day, the radar caught the enemy's missile attack, because the system was still in the trial stage. So a system may not be able to intercept all missiles.
Input the altitude of the missile in turn (the altitude given by the radar is a positive integer of no more than 30000). Calculate the minimum number of such missile interception systems required to intercept all missiles.
[input]
The height of N flying in sequence (1 ≤ n ≤ 1000).
[output]
The minimum number of systems to intercept all missiles k.
[input example]
389 207 155 300 299 170 158 65
[output example]
2
[tips]
Input: Missile Altitude: 4 # 3 # 2
Output: missile interception system k=1
[Title Analysis]
This problem is to find the minimum number of intercepting systems required for intercepting missiles. The minimum altitude in this question is very important. The minimum altitude of each interceptor system can be recorded. For the coming missiles, the interceptor system with the lowest altitude on the existing interceptor system can be selected for interception to ensure that the altitude of each interceptor system can be fully utilized.
[reference code]
#include<bits/stdc++.h>
using namespace std;
int a[100001];
int b[100001];//Minimum altitude of each interception system
int main() {
int n,sum=0;
while(scanf("%d",&n)==1)
a[++sum]=n;
int k=1;
b[1]=a[1];
for(int i=2; i<=sum; i++) {
//Find out whether the existing interception system can intercept
int minn=30001,x;
for(int j=1; j<=k; j++)
if(b[j]>=a[i]&&b[j]<=minn)
x=j,minn=b[j];
if(minn!=30001)//Update minimum height
b[x]=a[i];
else//Unable to intercept, add an interception system
b[++k]=a[i];
}
printf("%d",k);
return 0;
}Question 2: interceptor missile
[Title Description]
In order to defend against the missile attack of the enemy country, a certain country has developed a missile interception system. However, this missile interception system has a defect: although its first shell can reach any height, each shell in the future cannot be higher than the height of the previous one. One day, the radar caught the enemy's missile attack. Since the system is still in the trial stage, there is only one system, so it may not be able to intercept all missiles.
Input the altitude of the missiles in turn (the altitude data given by the radar is a positive integer of no more than 30000), and calculate the maximum number of missiles that the system can intercept.
[input]
The first line is an integer n (no more than 15), indicating the number of missiles.
The second line contains N integers, which are the altitude of the missile in turn (the altitude data given by the radar is a positive integer not greater than 30000).
[output]
An integer indicating the maximum number of missiles that can be intercepted.
[input example]
8 389 207 155 300 299 170 158 65
[output example]
6
[Title Analysis]
This question asks us to find out how many missiles an interception system can intercept at most. We can calculate from the time we go: the first interception system can only intercept one, and the following 2~n interception systems only need to find the interception system with a height greater than and the largest number of interceptions in 1~i-1 as the interception number of the i-th interception system
[reference code]
#include<bits/stdc++.h>
using namespace std;
int a[100001];
int c[100001];//Number of interceptions per system
int main() {
int sum=0;
scanf("%d",&sum);
for(int i=1; i<=sum; i++)
scanf("%d",&a[i]);
c[sum]=1;
int maxx=-1;
for(int i=1; i<=sum; i++) {
c[i]=1;
for(int j=1; j<i; j++)
if(a[j]>=a[i]&&c[j]>=c[i])
c[i]=c[j]+1;//Be careful not to forget to add one
maxx=max(maxx,c[i]);
}
printf("%d",maxx);
return 0;
}Question 2: 1260: [example 9.4] interceptor missile (Noip 1999)
[Title Description]
In order to defend against the missile attack of the enemy country, a certain country has developed a missile interception system. However, this missile interception system has a defect: although its first shell can reach any height, each shell in the future cannot be higher than the height of the previous one. One day, the radar caught the enemy's missile attack. Since the system is still in the trial stage, there is only one system, so it may not be able to intercept all missiles.
Input the altitude of the missiles in turn (the altitude data given by the radar is a positive integer of no more than 30000, and the number of missiles does not exceed 1000), and calculate the maximum number of missiles that can be intercepted by this system and the minimum number of such missile interception systems if all missiles are to be intercepted.
[input]
Enter the altitude of the missile in turn.
[output]
Line 1: the maximum number of missiles that can be intercepted;
Line 2: the minimum number of systems to intercept all missiles.
[input example]
389 207 155 300 299 170 158 65
[output example]
6 2
[Title Analysis]
This problem only needs to connect the above two problems. Look at the code directly
[reference code]
#include<bits/stdc++.h>
using namespace std;
int a[100001];
int b[100001];//Minimum altitude of each interception system
int c[100001];//Number of missiles that can be intercepted by each system
int main() {
int n,sum=0;
while(scanf("%d",&n)==1)
a[++sum]=n;
//Maximum number
c[sum]=1;
int maxx=-1;
for(int i=1; i<=sum; i++) {
c[i]=1;
for(int j=1; j<i; j++)
if(a[j]>=a[i]&&c[j]>=c[i])
c[i]=c[j]+1;
maxx=max(maxx,c[i]);
}
printf("%d\n",maxx);
//Number of interception systems
int k=1;
b[1]=a[1];
for(int i=2; i<=sum; i++) {
//Find out whether the existing interception system can intercept
int minn=30001,x;
for(int j=1; j<=k; j++)
if(b[j]>=a[i]&&b[j]<=minn)
x=j,minn=b[j];
if(minn!=30001)
b[x]=a[i];
else
b[++k]=a[i];
}
printf("%d",k);
return 0;
}