鏈接：https://www.luogu.org/problemnew/show/P2766
思路：首先第一問用n^2的dp求出，第二問用網(wǎng)絡(luò)流做，因為每個點只能用一次相當(dāng)于結(jié)點上有限制，所以需要拆點，左邊的點負責(zé)接輸入，右邊的點負責(zé)輸出，中間拉一條容量為1的邊，然后源點到每個dp[i] = 1的點都拉一條邊，表示開始，所有dp[i] = res(一問答案)的點到匯點拉一條邊，表示結(jié)束，跑一遍網(wǎng)絡(luò)流即可。第三問不能重新建圖會超時，直接把源點到1的邊變?yōu)闊o窮，1拆的兩個點之間的邊變?yōu)闊o窮，n如果跟匯點有邊就把邊變?yōu)闊o窮，n拆的兩個點間變?yōu)闊o窮，跑的最大流加上第二問的答案就是第三問的答案。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010;
const int INF  = 1e9;
int n;
int a[maxn];

struct edge{
    int from,to,cap,flow;
};

struct Dinic{
    int n,m,s,t;
    vector<int> G[maxn];
    vector<edge> edges;
    int d[maxn];
    int cur[maxn];
    bool vis[maxn];

    void init(int n){
        this->n = n;
        for(int i=0;i<=n;i++)G[i].clear();
        edges.clear();
    }

    void addedge(int from,int to,int cap){
        edges.push_back(edge{from,to,cap,0});
        edges.push_back(edge{to,from,0,0});
        m = edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }

    bool bfs(){
        memset(vis,0,sizeof(vis));
        d[s] = 0;
        vis[s] = 1;
        queue<int> q;
        q.push(s);
        while(!q.empty()){
            int x = q.front();
            q.pop();
            for(int i=0;i<G[x].size();i++){
                edge &e = edges[G[x][i]];
                if(!vis[e.to]&&e.cap>e.flow){
                    vis[e.to] = 1;
                    d[e.to] = d[x] + 1;
                    q.push(e.to);
                }
            }
        }
        return vis[t];
    }

    int dfs(int x,int a){
        if(x==t||a==0)return a;
        int flow = 0,f;
        for(int &i = cur[x];i<G[x].size();i++){
            edge &e = edges[G[x][i]];
            if(d[x] + 1==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0){
                e.flow+=f;
                edges[G[x][i]^1].flow-=f;
                flow+=f;
                a-=f;
                if(!a)break;
            }
        }
        return flow;
    }

    int maxflow(int s,int t){
        this->s = s;
        this->t = t;
        int flow = 0;
        while(bfs()){
            memset(cur,0,sizeof(cur));
            flow+=dfs(s,INF);
        }
        return flow;
    }
}solver;

int dp[maxn];

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++)dp[i] = 1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
           if(a[j]<=a[i])dp[i] = max(dp[i],dp[j] + 1);
    }
    }
    int res = 0;
    for(int i=1;i<=n;i++){
        res = max(res,dp[i]);
    }

    solver.init(2*n+1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
            if(a[j]<=a[i]&&dp[j]+1==dp[i])//一定要兩個條件都確保才能建邊
solver.addedge(j+n,i,1);
        }
    }
    for(int i=1;i<=n;i++){
        solver.addedge(i,i+n,1);
        if(dp[i]==res){
            solver.addedge(i+n,2*n+1,1);
        }
        if(dp[i]==1)solver.addedge(0,i,1);
    }
    int res1 = solver.maxflow(0,2*n+1);

    solver.addedge(0,1,INF);
    solver.addedge(1,1+n,INF);
    if(dp[n]==res){//如果有邊則加一條容量為無窮的邊
        solver.addedge(n,2*n,INF);
        solver.addedge(2*n,2*n+1,INF);
    }
    int res2 = res1 + solver.maxflow(0,2*n+1);
    printf("%d\n%d\n%d\n",res,res1,res2);
    return 0;
}