1. 题目

传送门=￣ω￣=

2. 题解

建模真奇妙。

（同时这是我打的第一个真·Dinic，以前被骗了一直在打 BFS 版的增广路算法。。。）

第一问用 dp 解决就行了。

第二问就得网络流。

首先我们把 $1,2,3,…,n$这些位置每个位置拆成两个点，我们设它们为 $(1,a),(1,b),(2,a),(2,b),(3,a),(3,b),…,(n,a),(n,b)$

接着我们在 $(i,a),(i,b)$这两个点之间连一条容量为 1 的边，从 $(i,a)$指向 $(i,b)$。

然后设第 $i$个位置之前（必须含第 $i$个位置）的最长不降子序列长度为 $f[i]$。

则如果 $f[i]=1$则从源点连一条容量为 1 的边到 $(i,a)$

如果 $f[i]=$第一问答案则从 $(i,b)$连一条容量为 1 的边到汇点。

如果 $i<j$且 $h[i]\leq h[j]$且 $f[i]+1=f[j]$则从 $(i,b)$连一条容量为 1 的边到 $(j,a)$

建图完毕，跑最大流就是第二问答案。

第三问的话就是在第二问建的图中，把 $(1,a)->(1,b),(n,a)->(n,b),$源点 $->(1,a),(n,b)->$汇点的边的容量改为无限大（如果这些边存在的话），再跑最大流就是答案。

为什么呢？不难发现我们是在能进行状态转移的状态之间连边。因为子序列不能重合，所以每个位置只能选一次，所以我们就把每个位置拆成两个点来控制一个点只能被选 1 次。

对于第三问，第一个位置和第 $n$个位置可以选无数次，则改掉控制它们的边就行了。

真奇妙。

代码：

#include <bits/stdc++.h>
using namespace std;
struct edge{int u,v,c;}e[1000005];
int n,h[505],f[505],s=1,T,cnt,ans,cur[1005],dep[1005];
vector<int> g[1005];
queue<int> que;
void adde(int a,int b,int c)
{
    g[a].push_back(cnt),e[cnt++]=(edge){a,b,c};
    g[b].push_back(cnt),e[cnt++]=(edge){b,a,0};
}
bool bfs()
{
    while(!que.empty())que.pop();
    memset(dep,0,sizeof(dep)),que.push(0),dep[0]=1;
    while(!que.empty())
    {
        int F=que.front();que.pop();
        for(vector<int>::iterator i=g[F].begin();i!=g[F].end();i++)
            if(!dep[e[*i].v]&&e[*i].c)
                que.push(e[*i].v),dep[e[*i].v]=dep[F]+1;
        if(dep[T])return 1; 
    }
    return 0;
} 
int dfs(int a,int F)
{
    if(a==T)return F;
    for(int j,tmp;cur[a]<g[a].size();cur[a]++)
        if(j=g[a][cur[a]],dep[a]+1==dep[e[j].v]&&e[j].c)
        {
            tmp=dfs(e[j].v,min(F,e[j].c));
            if(tmp){e[j].c-=tmp,e[j^1].c+=tmp;return tmp;}
        }
    return 0;
}
int main()
{
    scanf("%d",&n),T=n<<1|1;
    for(int i=1;i<=n;i++)scanf("%d",&h[i]);
    for(int i=1;i<=n;i++)
    {
        f[i]=1;
        for(int j=1;j<i;j++)if(h[j]<=h[i])
            s=max(s,f[i]=max(f[i],f[j]+1));
    }
    printf("%d\n",s);
    for(int i=1;i<=n;i++)if(f[i]==1)adde(0,i,1);
    for(int i=1;i<=n;i++)if(f[i]==s)adde(i+n,T,1);
    for(int i=1;i<=n;i++)adde(i,i+n,1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
            if(h[j]<=h[i]&&f[j]+1==f[i])adde(j+n,i,1);
    while(bfs())
    {
        memset(cur,0,sizeof(cur));
        int tmp;
        while(tmp=dfs(0,1e8),tmp)ans+=tmp;
    }
    printf("%d\n",ans),g[0].clear(),g[T].clear();
    for(int i=1;i<=n;i++)g[i].clear(),g[i+n].clear();
    ans=cnt=0,adde(1,1+n,1e8),adde(n,n<<1,1e8);
    if(f[1]==1)adde(0,1,1e8);
    if(f[n]==s)adde(n<<1,T,1e8);
    for(int i=2;i<=n;i++)if(f[i]==1)adde(0,i,1);
    for(int i=1;i<n;i++)if(f[i]==s)adde(i+n,T,1);
    for(int i=2;i<n;i++)adde(i,i+n,1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
            if(h[j]<=h[i]&&f[j]+1==f[i])adde(j+n,i,1);
    while(bfs())
    {
        memset(cur,0,sizeof(cur));
        int tmp;
        while(tmp=dfs(0,1e8),tmp)ans+=tmp;
    }
    printf("%d\n",ans);
    return 0;
}