求助!!!82分!!!

P2766 最长不下降子序列问题

HNYLMS_MuQiuFeng @ 2018-11-24 10:00:14

//Code by muq
#include<set>
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
#define mp make_pair
#define lll long long
#define inf 2147483647
#define pii pair<int,int>
#define io0 ios::sync_with_stdio(0)
#define ppi pair<pair<int,int>,int>
#define me(a,b) memset(a,b,sizeof(a))
#define reph(i,a,b) for(i=a;i<=b;++i)
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define rap(i,a,b) for(int i=a;i>=b;--i)
#define repp(i,a,b,c) for(int i=a;i<=b;i+=c)
#define lrep(i,a,b) for(long long i=a;i<=b;++i)
#define reg(i,d,head,a) for(int i=head[d];i;i=a[i].next)

using namespace std;

inline void File() {
    freopen("muq.in.txt", "r", stdin);
}

int n, s, t, head[500010], nu[600], cur[500010];//一开始把nu(存输入数字的数组)习惯性的定义为a然后存边数组也为a就咕了……
int cnt = 1, dep[500010], dp[600], ma;
int ans1, ans2;

struct edge {
    int next, to, wt;
} a[500010];

inline void add(int u, int v, int w) {
    a[++cnt] = (edge) {head[u], v, w};
    head[u] = cnt;
}

inline void addedge(int u, int v, int w) {
    add(u, v, w);
    add(v, u, 0);
}

inline int dfs(int u, int flow) {
    if(u == t)
        return flow;
    for(int &i = cur[u]; i; i = a[i].next) {
        int to = a[i].to;
        if(dep[to] == dep[u] + 1 and a[i].wt) {
            int di = dfs(to, min(a[i].wt, flow));
            if(di > 0) {
                a[i].wt -= di;
                a[i^1].wt += di;
                return di;
            }
        }
    }
    return 0;
}

inline bool bfs() {
    queue <int> q;
    me(dep, 0);
    dep[s] = 1;
    q.push(s);
    do {
        int u = q.front();
        q.pop();
        reg(i, u, head, a) {
            int to = a[i].to;
            if(dep[to] == 0 and a[i].wt > 0) {
                dep[to] = dep[u] + 1;
                q.push(to);
            }
        }
    }while(!q.empty());
    return dep[t];
}

inline int Dinic() {
    int ans = 0;
    while(bfs()) {
        rep(i, 0, t) {
            cur[i] = head[i];
        }
        while(int d = dfs(s, inf)) {
            ans += d;
        }
    }
    return ans;
}

int main(void) {
    //File();

    io0;

    cin >> n;
    s = 0, t = 2 * n + 1;//开始没写真尴尬……还好想起来了不然要凉2333
    rep(i, 1, n) {
        cin >> nu[i];
        dp[i] = 1;
    }
    rep(i, 1, n) {
        rep(j, 1, i - 1) {
            if(nu[j] <= nu[i])
                dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    rep(i, 1, n)
        ma = max(ma, dp[i]);
    rep(i, 1, n) {
        if(dp[i] == 1)
            addedge(s, i, 1);
        else if(dp[i] == ma)
            addedge(i + n, t, 1);
    }
    rep(i, 1, n) {
        addedge(i, i + n, 1);
    }
    rep(i, 1, n) {
        rep(j, 1, i - 1) {
            if(nu[j] <= nu[i] and dp[i] == dp[j] + 1)
                addedge(j + n, i, 1);
        }
    }
    ans1 = Dinic();
    addedge(s, 1, inf);
    addedge(1, n + 1, inf);//写成(n+1,t,inf)……
    if(dp[n] == ma) {//如果最后一个数能作为一个最长不下降子序列的终点
        addedge(n, n * 2, inf);//一开始写成(s,n,inf)我是不是没救了
        addedge(n * 2, t, inf);
    }
    ans2 = Dinic() + ans1;//这里要加上原来的答案!
    cout << ma << endl << ans1 << endl << ans2 << endl;
    return 0;
}

哪里错了QAQ


by HNYLMS_MuQiuFeng @ 2018-11-24 12:37:48

@隔壁小邱 Dinic要是有错的话那是哪里呢???求助


by SkyLiYu @ 2018-11-24 18:11:49

@HNYLMS_MuQiuFeng 我没说你dinic有错Q#Q


by SkyLiYu @ 2018-11-24 18:12:50

@HNYLMS_MuQiuFeng 没有数据怎么搞...要不您rand()拍一下吧


by HNYLMS_MuQiuFeng @ 2018-11-24 20:22:09

@隔壁小邱 emmm好叭……明天改


by w4p3r @ 2018-12-02 22:46:57

    rep(i, 1, n) {
        if(dp[i] == 1)
            addedge(s, i, 1);
        else if(dp[i] == ma)
            addedge(i + n, t, 1);
    }

这里的else应该去掉,因为如果这是一个递减的数组(如5 4 3 2 1),ma就会等于1,这时候每个点都应该既对源点建边也对汇点建边,但是这个else会使每个点只和源点建边。
我才不会告诉你我也是这里错了qwq


by nosta @ 2018-12-12 22:03:44

@Waper 这么巧,我也错这地儿了。。


by w4p3r @ 2018-12-12 23:30:30

@nosta 23333


by Smokey_Days @ 2019-01-06 20:47:44

@Waper 感谢您提供的全新思路(大雾)


by 斯茂 @ 2019-02-12 20:00:18

特判一个第一问答案为1就好了


上一页 |