题解 P1410 【子序列】

GF072 · 2020-10-02 13:56:10 · 题解

根据抽屉原理，如果存在3个逆序的数字，则一定无法分到两个队列。相反如果只有两个逆序数字及以下，则可以分为两个队列。逆向思维后题目复杂度极大降低，只需要找一个最长的逆向序列即可，最简单的动态规划，复杂度O(N*N)。

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int N, a[2001], f[2001];
    bool res;
    while(cin>>N){
        res=true;
        for(int i=0;i<N;i++){
            cin>>a[i];
            f[i]=1;
            for(int j=i-1;j>=0;j--){
                if(a[i]<a[j]){
                    f[i]=max(f[i],f[j]+1); 
                }
            }
            if(f[i]>2){
                res=false;
            }
        }
        if(res){
            cout<<"Yes!"<<endl;
        }else{
            cout<<"No!"<<endl;
        }
    }
}