题解 P1410 【子序列】

asuldb · 2018-08-08 08:18:29 · 题解

分成两个子序列的话，我们很容易就联想到了二分图

如果一个数后面有一个小于等于它的数，那么这两个数一定不能在同一个子序列里

于是我们判断两个元素能否处在同一个严格递增的子序列里，如果不能就将这两个元素连一条边，最后跑一边dfs染色就好了

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#define re register
#define maxn 2001
using namespace std;
struct node
{
    int v,nxt;
}e[maxn*maxn];
int n,m,num;
int head[maxn],a[maxn],c[maxn];
inline void add_edge(int x,int y)
{
    e[++num].v=y;
    e[num].nxt=head[x];
    head[x]=num;
}
inline int read()
{
    char c=getchar();
    int x=0;
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9')
      x=(x<<3)+(x<<1)+c-48,c=getchar();
    return x;
}
bool dfs(int x,int co)
{
    c[x]=co;
    int ch=0;
    for(re int i=head[x];i;i=e[i].nxt)
    if(c[e[i].v]==-1) 
    {
        ch=dfs(e[i].v,co^1);
        if(ch) return 1;
    }else if(c[e[i].v]==c[x]) return 1;//如果同一个颜色的两个点有边相连，那么这个图不是二分图
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(re int i=1;i<=n;i++)
            a[i]=read();
        memset(head,0,sizeof(head));
        num=0;
        for(re int i=1;i<=n;i++)
        for(re int j=i+1;j<=n;j++)
        if(a[j]<=a[i]) add_edge(i,j),add_edge(j,i);
        memset(c,-1,sizeof(c));
        int flag=0;
        for(re int i=1;i<=n;i++)//图有可能不连通
        if(c[i]==-1) //还没被染色
        {
            flag=dfs(i,1);
            if(flag) break;
        } 
        if(flag) puts("No!");
        else puts("Yes!");
    }
    return 0;
}