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,c};
}
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;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

1 条评论

【算法】 网络流算法之Binic算法 「半娱乐向」 | K-XZY · 2017年11月26日 4:32 下午

[…] 具体做法已经在这篇博客->传送门= ̄ω ̄=讲过了,这里不做过多赘述。 […]

发表评论

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

你是机器人吗? =。= *