icontofig | 发布于 2019-07-07 11:01:45 | 阅读量 354 | 网络流 最大流
发布于 2019-07-07 11:01:45 | 网络流 最大流

题目描述

给定正整数序列x1,...,xn 。

(1)计算其最长不下降子序列的长度s。

(2)计算从给定的序列中最多可取出多少个长度为s的不下降子序列。

(3)如果允许在取出的序列中多次使用x1和xn,则从给定序列中最多可取出多少个长度为s的不下降子序列。

编程任务:

设计有效算法完成(1)(2)(3)提出的计算任务。

输入输出格式

输入格式:

第1 行有1个正整数n,表示给定序列的长度。接下来的1 行有n(n ≤ 500)个正整数n:x1, ..., xn。

输出格式:

第1 行是最长不下降子序列的长度s。第2行是可取出的长度为s 的不下降子序列个数。第3行是允许在取出的序列中多次使用x1和xn时可取出的长度为s 的不下降子序列个数。

样例输入

4
3 6 2 5

样例输出

2
2
3

题解

此题是经典的网络流24题之一。

对第一问,我们直接写O(n2)的DP即可,最长不下降子序列的DP转移方程不再给出,可以参考代码。

其实最长不下降子序列也是有O(nlogn)算法的,通常来说那种算法更优,不过在本题中并不适用,原因在于此题的后两问。

首先看第二问,要我们求出这个序列中能取出多少个长度为s(最长)的子序列?

很明显如果如同导弹拦截(最长不下降子序列的基础题)一样不断求最长不下降子序列是有可能超时的?

我们可以考虑使用最大流模型。

让dp值为1的点连向设置的源点S,dp值为s的店连向设置的源点T。

然后我们可以根据O(n2)DP的转移方程给图来建边,做成一个以到当前节点为止的最长不下降子序列长度分层的分层图。

这就是为什么不用O(nlogn)的算法的原因了。

不过我一开始还WA了,我还在想为啥……

结果因为我没写限流……简直真的跟zz一样。

限流的写法就是每个点拆成入点和出点,入点向出点连一条流量为1的边代表这个点上的数只能选取1次。然后对应出点-入点建流量为1的边。

如此第三问就是把S到1的入点,1的入点到1的出点的流量改为INF。而对于第n个点,如果dp值为s,则n的入点向n的出点、n的出点向T的流量改为INF就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num << 1) + (num<<3) + c - '0';
    return (flag ? -1 : 1) * num;
}
const int maxn = 505;
int S,T;
int n;
int a[maxn],f[maxn];
const int INF = 1e9;
struct Flow{
    int cnt;
    int h[maxn<<1],cur[maxn<<1];
    void init(){
        cnt = 0;
        memset(h,-1,sizeof(h));
        return;
    }
    struct edge{
        int to,next,cap;
    }e[maxn*maxn];
    void add(int u,int v,int c){
        e[cnt].to = v;e[cnt].next = h[u];e[cnt].cap = c;
        h[u] = cnt++;
        return;
    }
    int d[maxn];
    bool BFS(int s,int t){
        queue<int>q;
        for(int i = s;i <= t;++i)
            d[i] = INF;
        d[s] = 0;
        q.push(s);
        while(!q.empty()){
            int now = q.front();
            q.pop();
            for(int i = h[now];i != -1;i = e[i].next){
                int v = e[i].to;
                if(d[v] == INF && e[i].cap > 0){
                    d[v] = d[now] + 1;
                    q.push(v);
                }
            }
        }
        return (d[t] != INF);
    }
    int DFS(int now,int t,int a){
        if(now == t || a == 0)return a;
        int flow = 0,f;
        for(int &i = cur[now];i != -1;i = e[i].next){
            int v = e[i].to;
            if(e[i].cap > 0 && d[v] == d[now] + 1){
                f = min(a - flow,e[i].cap);
                f = DFS(v,t,f);
                flow += f;
                e[i].cap -= f;
                e[i^1].cap += f;
                if(flow == a)return flow;
            }
        }
        return flow;
    }
    int dinic(int s,int t){
        int flow = 0;
        while(BFS(s,t)){
            for(int i = s;i <= t;++i)cur[i] = h[i];
            flow += DFS(s,t,INF);
        }
        return flow;
    }
}dc,dc2;
int main(){
    n = get_num();
    for(int i = 1;i <= n;++i){
        a[i] = get_num();
        f[i] = 1;
    }
    for(int i = 2;i <= n;++i){
        for(int j = 1;j < i;++j){
            if(a[i] >= a[j])
                f[i] = max(f[i],f[j] + 1);
        }
    }
    int ans = 1;
    for(int i = 1;i <= n;++i){
        ans = max(ans,f[i]);
    }
    printf("%d\n",ans);
    dc.init();
    S = 0;
    T = 2*n+1;
    for(int i = 1;i <= n;++i){
        if(f[i] == 1){
            dc.add(S,i,1);
            dc.add(i,S,0);
        }
        if(f[i] == ans){
            dc.add(i+n,T,1);
            dc.add(T,i+n,0);
        }
    }
    for(int i = 1;i <= n;++i){
        dc.add(i,i+n,1);dc.add(i+n,i,0);
    }
    for(int i = 2;i <= n;++i){
        for(int j = 1;j < i;++j){
            if(f[i] == f[j] + 1 && a[i] >= a[j]){
                dc.add(j+n,i,1);
                dc.add(i,j+n,0);
            }
        }
    }
    int ansx = dc.dinic(S,T);
    printf("%d\n",ansx);
    dc.add(S,1,INF);dc.add(1,S,0);
    dc.add(1,n+1,INF);dc.add(1+n,1,0);
    if(f[n] == ans && n != 1){
        dc.add(n,n*2,INF);dc.add(n*2,n,0);
        dc.add(2*n,T,INF);dc.add(T,2*n,0);
    }
    printf("%d\n",ansx+dc.dinic(S,T));
    return 0;
}

 

 


内容更新于: 2019-11-05 20:43:04
链接地址: http://blog.leanote.com/post/icontofig/%E7%BD%91%E7%BB%9C%E6%B5%8124%E9%A2%98-%E4%B9%8B-%E6%9C%80%E9%95%BF%E4%B8%8D%E4%B8%8B%E9%99%8Dzi-xue-lie

上一篇: BZOJ 3156 防御准备 决策单调性斜率优化DP

下一篇: BZOJ 1999 树网的核[数据加强版] 树的直径+线段树

354 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航