P1410 子序列 题解

李林恺 · 2020-03-04 09:59:25 · 题解

思路：贪心

这题其实和导弹拦截一样，可以用贪心做。

一边读入，一边判断每一个数

如果比第一个子序列的最大值大，那么就加入第一个子序列，子序列的最大值也变为那个数

如果比第二个子序列的最大值大并且这个数没有加入第一个子序列，那么就加入第二个子序列，子序列的最大值也变为那个数

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
    while(cin>>n){
        int f=1,x=0,y=0,z=0,z2=0;
        for(int i=1;i<=n;i++){
            int t,ff=1;
            cin>>t;
            if(t>x) x=t,z++,ff=0;
            if(t>y&&ff) y=t,z2++,ff=0;
            if(ff) f=0;
        }
        if(f) cout<<"Yes!"<<endl;
        else cout<<"No!"<<endl;
    }
    return 0;
}