P2766 最长不下降子序列问题(网络流24题)

题目链接

https://www.luogu.org/problem/P2766

解题思路

https://www.luogu.org/blog/PopulusEuphratica/luogup2766-zui-zhang-fou-xia-xiang-zi-xu-lie-wen-ti

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e2+100;
const int inf=0x3f3f3f3f;
int a[maxn],dp[maxn];
int n;
struct node {
    int v,nxt,w;
} edge[maxn*maxn];
int head[maxn*2],cur[maxn*2],dep[maxn*2];
int tot=0,maxflow=0;
void add(int u,int v,int w) {
    edge[tot]= {v,head[u],w};
    head[u]=tot++;
    edge[tot]= {u,head[v],0};
    head[v]=tot++;
}
bool bfs(int s,int t) {
    memset(dep,-1,sizeof(dep));
    queue<int>q;
    dep[s]=0;
    q.push(s);
    while(!q.empty()) {
        int now=q.front();
        q.pop();
        for(int i=head[now]; i!=-1; i=edge[i].nxt) {
            if(dep[edge[i].v]==-1&&edge[i].w>0) {
                dep[edge[i].v]=dep[now]+1;
                q.push(edge[i].v);
                if(edge[i].v==n+n+1)
                    return 1;
            }
        }
    }
    return false;
}
int dfs(int now,int t,int limit) {
    if(!limit||now==t) {
        return limit;
    }
    int flow=0,f=0;
    for(int i=cur[now]; i!=-1; i=edge[i].nxt) {
        cur[now]=i;
        if(dep[edge[i].v]==dep[now]+1&&(
                    f=dfs(edge[i].v,t,min(limit,edge[i].w)))) {
            flow+=f;
            limit-=f;
            edge[i].w-=f;
            edge[i^i].w+=f;
            if(!limit)
                break;
        }
    }
    return flow;
}
void dinic(int s,int t) {
    while(bfs(s,t)) {
        memcpy(cur,head,sizeof(head));
        maxflow+=dfs(s,t,inf);
    }
}
int main() {
    ios::sync_with_stdio(false);
    memset(head,-1,sizeof(head));
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>a[i];
    }
    int ansa=0;
    for(int i=1; i<=n; i++) {
        dp[i]=1;
        for(int j=i-1; j>=1; j--) {
            if(a[j]<=a[i]&&dp[j]+1>dp[i]) {
                dp[i]=dp[j]+1;
            }
        }
        ansa=max(ansa,dp[i]);
    }
    cout<<ansa<<endl;
    for(int i=1; i<=n; i++) {
        add(i,i+n,1);
        if(dp[i]==1)
            add(0,i,1);
        if(dp[i]==ansa)
            add(i+n,n+n+1,1);
        for(int j=1; j<i; j++) {
            if(a[j]<=a[i]&&dp[j]==dp[i]-1) {
                add(j+n,i,1);
            }
        }
    }
    maxflow=0;
    dinic(0,n+n+1);
    cout<<maxflow<<endl;
    add(0,1,0x3f3f3f3f);
    add(1,n+1,0x3f3f3f3f);
    if(dp[n]==ansa) {
        add(n,n+n,0x3f3f3f3f);
        add(n+n,n+n+1,0x3f3f3f3f);
    }
    dinic(0,n+n+1);
    cout<<maxflow<<endl;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注