hack

5
2 1 3 5 4

卡掉我这种不拆点做法

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<map>
#include<bitset>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int n,ans,s,t,maxf;
int cur[510],dep[510],a[510],dp[510];
int tot=1,head[510];
struct EDGE
{
    int nxt,to,val;
}edge[500010];
inline void add(int u,int v,int val)
{
    edge[++tot].nxt=head[u];
    edge[tot].to=v;
    edge[tot].val=val;
    head[u]=tot;
}
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline bool bfs()
{
    queue<int> que;
    for(int i=s;i<=t;++i) dep[i]=0,cur[i]=head[i];
    dep[s]=1;
    que.push(s);
    while(!que.empty())
    {
        int x=que.front();que.pop();
        for(int i=head[x];i;i=edge[i].nxt)
        {
            int y=edge[i].to;
            if(dep[y]||edge[i].val==0) continue;
            dep[y]=dep[x]+1;
            que.push(y);
            if(y==t) return 1;
        }
    }
    return 0;
}
int dfs(int x,int in)
{
    if(x==t) return in;
    int out=0;
    for(int &i=cur[x];i;i=edge[i].nxt)
    {
        int y=edge[i].to;
        if(dep[y]!=dep[x]+1||edge[i].val==0) continue;
        int res=dfs(y,min(in,edge[i].val));
        edge[i].val-=res;
        edge[i^1].val+=res;
        in-=res;
        out+=res;
        if(in==0) return out;
    }
    if(out==0) dep[x]=0;
    return out;
}
int main()
{
    n=read();
    s=0,t=n+1;
    ans=0;
    for(int i=1;i<=n;++i)
    {
        a[i]=read();
        dp[i]=1;
        for(int j=1;j<i;++j)
        {
            if(a[i]>=a[j]) dp[i]=max(dp[i],dp[j]+1);
        }
        ans=max(dp[i],ans);
    }
    if(n==1)
    {
        printf("1\n1\n1\n");
        return 0;
    }
    printf("%d\n",ans);
    for(int i=1;i<=n;++i)
    {
        if(dp[i]==1)
            add(s,i,1),add(i,s,0);
        if(dp[i]==ans)
            add(i,t,1),add(t,i,0);
        for(int j=1;j<i;++j)
        {
            if(a[i]>=a[j]&&dp[i]==dp[j]+1)
                add(j,i,1),add(i,j,0);
        }
    }
    maxf=0;
    while(bfs()) maxf+=dfs(s,inf);
    printf("%d\n",maxf);
    if(dp[1]==1) add(s,1,inf),add(1,s,0);
    if(dp[n]==ans) add(n,t,inf),add(t,n,0);
    while(bfs()) maxf+=dfs(s,inf);
    printf("%d\n",maxf);
    return 0;
}