P1410 子序列 题解

· · 题解

解题思路

这道题要求将原序列分为两部分，这启发我们想到二分图。

遍历一遍所有元素，将所有满足 a_i\geq a_j 且 i<j 的点对 (i,j) 之间连边，跑二分图染色。

如果染色全部成功，那么说明原序列能被划分成两段严格递增子序列。

这个时候直接输出 Yes! 或 No! 是存在谬误的，因为“原序列能被划分成两段严格递增子序列”是“原序列能被划分成两段均为 \frac{n}{2} 的严格递增子序列”的必要条件，并不与原命题等价。

我们考虑一个可行性背包 DP。

记建好图后连通块总数为 cnt，记 w_{i,0/1} 为第 i 个连通块染黑/白色点的数量，每组 w 必须选择一个。

定义 f_{i,j} 为对于前 i 个连通块，选取了 j 个点作为左部点是否有解。有解记为 1，无解记为 0,并同时定义 f_{0,0}=1。

转移部分很好写，都是一些套路，就不展开了。

最后判断 f_{cnt,\frac{n}{2}} 是否为 1，是的话输出 Yes!，否则输出 No!。

时间复杂度约为 O(n^2)，可以通过本题。

参考代码

#include<iostream>
#include<cstring>
using namespace std;
const int N=4e6+10;
struct node{
    int to,nxt; 
}edge[2*N];
int head[5005];
int cnt;
void add(int u,int v){
    edge[++cnt]={v,head[u]};
    head[u]=cnt;
}
bool vst[5005];
bool f[5005][5005];
int a[5005],col[5005];
int w[5005][2];
bool flag;
int n,bl;
void dfs(int x){
    vst[x]=true;
    w[bl][col[x]]++;
    for(int i=head[x];i!=-1;i=edge[i].nxt){
        if(!flag) return;
        if(vst[edge[i].to]){
            if(col[edge[i].to]!=col[x]^1){
                flag=false;
                return;
            }
        }else{
            col[edge[i].to]=col[x]^1;
            dfs(edge[i].to);
        }       
    }
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>n){
        memset(head,-1,sizeof(head));
        memset(vst,0,sizeof(vst));
        memset(col,0,sizeof(col));
        memset(f,0,sizeof(f));
        memset(w,0,sizeof(w));
        cnt=bl=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                if(a[i]>a[j]){
                    add(j,i);
                    add(i,j);
                }
            }
        }
        flag=true;
        for(int i=1;i<=n;i++){
            if(!vst[i]){
                bl++; 
                dfs(i);
            }
        }
        if(!flag) cout<<"No!\n";
        else{
            f[0][0]=1;
            for(int i=1;i<=bl;i++){
                for(int j=0;j<=n;j++){
                    if(j>=w[i][0]) f[i][j]|=f[i-1][j-w[i][0]];
                    if(j>=w[i][1]) f[i][j]|=f[i-1][j-w[i][1]];
                }
            }
            if(f[bl][n/2]) cout<<"Yes!\n";
            else cout<<"No!\n";
        }
    }
    return 0;
}

本代码可以通过原题数据评测。

通过讨论区广泛认同的 hack 数据 的记录：record。

与之对比的错误二分图做法记录：record 以及 code。

Written by toolong114514 on 2024/8/24.