AcWing 1010. 拦截导弹
原题链接
简单
作者:
梨小畅
,
2021-05-08 22:54:03
,
所有人可见
,
阅读 258
法1:贪心 + 栈
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
const int N=1010;
int a[N],f[N];
stack <int> st[N];
int main(){
int t=0;
while(1){
int x=-1;
cin>>x;
if(x==-1) break;
a[++t]=x;
}
f[1]=a[1];
int l=1,res=1;
for(int i=2;i<=t;i++){
if(a[i]>a[i-1]) res++;
if(a[i]<=f[l]) f[++l]=a[i];
else{
int j=lower_bound(f+1,f+l+1,a[i],greater<int>())-f;
f[j]=a[i];
}
}
int kind=1;
st[1].push(a[1]);
for(int i=2;i<=t;i++){
int flag=0;
for(int j=1;j<=kind;j++)
if(a[i]<=st[j].top()) {
flag=1;
st[j].push(a[i]);
break;
}
if(flag==0) st[++kind].push(a[i]);
}
// 栈这部分 可以优化为 LIS
cout<<l<<endl<<kind;
return 0;
}
法2: 贪心
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
int a[N],f[N],b[N];
int main(){
int t=0;
while(1){
int x=-1;
cin>>x;
if(x==-1) break;
a[++t]=x;
}
f[1]=b[1]=a[1];
int l=1,kind=1;
for(int i=2;i<=t;i++){
if(a[i]>b[kind]) b[++kind]=a[i]; // 系统数 最终其实是: 最长单调递增子序列的长度
else {
int j=lower_bound(b+1,b+kind+1,a[i])-b;
b[j]=a[i];
}
if(a[i]<=f[l]) f[++l]=a[i];
else{
int j=lower_bound(f+1,f+l+1,a[i],greater<int>())-f;
f[j]=a[i];
}
}
cout<<l<<endl<<kind;
return 0;
}