问题描述
问题分析
考虑若使炮弹命中最多，则炮弹命中导弹的导弹递减
所以需要发射LIS次，以为代表无法调整使其命中更多
n2一般dp算法：
对于每一个a[i]判断a[0i]能否把它更新成dp[j]+1
也就是看a[i]能否加在a[0i]中的某个数之后
达到一个新的最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include<stdio.h>
int a[30200],dp[30200];
int main() {
int n;
while(scanf("%d",&n)!=EOF) {
for(int i=0; i<n; i++) {
dp[i]=1;
scanf("%d",&a[i]);
}
int res=0;
for(int i=1; i<n; i++)
for(int j=0; j<i; j++)
if(a[i]>a[j]&&dp[i]<dp[j]+1) {
dp[i]=dp[j]+1;
if(res<dp[i])
res=dp[i];
}
printf("%d\n",res);
}
return 0;
}
|
nlogn二分算法：
建一个数组保存取的数列的可能性
然后每判断到一个a[i]在s中找到一个s[k]<a[i]<s[k+1]的位置
然后用a[i]替换掉s[k+1]
也就是尽量用小的把使子序列相同的长度替换掉
这样可以保证后面的数比前面的数大的可能性提升
如果查找到s最后还没有a[i]<s[k+1]
则说明a[i]比目前s[k]的每一个数都大
这时候显然要把a[i]加到s的最后面
因为s中的数必然是单调递增的
所以在寻找位置的时候可以进行二分搜索优化时间
二分搜索的实现可以自己写函数
也可以调用C++中的lower_bound
自建函数：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include <stdio.h>
int inf=99999999;
int n,l;
int a[30200];
int s[30200];
int find(int m) {
int la=0,lb=l;
while(lb>=la) {
int mid=(la+lb)>>1;
if(s[mid]==m)
return mid;
else if(s[mid]>m)
lb=mid-1;
else
la=mid+1;
}
return la;
}
int main() {
while(scanf("%d",&n)!=EOF) {
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
s[0]=-1;
l=1;
for(int i=1; i<=n; i++) {
s[l]=inf;
int t=find(a[i]);
if(t==l)
l++;
s[t]=a[i];
}
printf("%d\n",l-1);
}
return 0;
}
|
运用C++函数：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <stdio.h>
#include <algorithm>
using namespace std;
int inf=99999999;
int a[30200],s[30200];
int main() {
int n;
while(scanf("%d", &n)!=EOF) {
for(int i=1; i<=n; i++)
scanf("%d",&a[i]),s[i]=inf;
int l=1;
for(int i=1; i<=n; i++) {
int k=lower_bound(s+1,s+n+1,a[i])-s;
if(k==l)
l++;
s[k]=a[i];
}
printf("%d\n",l-1);
}
return 0;
}
|