第三问过不了QAQ

P2766 最长不下降子序列问题

Winter_coming @ 2018-03-12 22:34:54

dalao帮帮忙,代码如下

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1086;
const int maxm=20086;
const int inf=99999999;
int head[maxn],to[maxm],from[maxm],next[maxm],w[maxm];
int cur[maxn],cnt=-1,b,k,l,n,m,dep[maxn],s,t;
int val[maxn],f[maxn],ass;
inline void add(int x,int y,int z){
    to[++cnt]=y;w[cnt]=z;next[cnt]=head[x];head[x]=cnt;from[cnt]=x;
    to[++cnt]=x;w[cnt]=0;next[cnt]=head[y];head[y]=cnt;from[cnt]=y;
}
inline int Read(){
    int x=0;char c=getchar();
    while (!isdigit(c)){
        c=getchar();
    }
    while (isdigit(c)){
        x=(x<<1)+(x<<3)+c-48;
        c=getchar();
    }return x;
}
bool bfs(){
    queue<int> q;
    memset(dep,0,sizeof(dep));
    q.push(s);dep[s]=1;
    while (!q.empty()){
        int u=q.front();q.pop();
        for (int i=head[u];i!=-1;i=next[i]){
            int v=to[i];
            if (dep[v]==0&&w[i]>0){
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }
    if (dep[t])return 1;
    else return 0;
}
inline int dfs(int x,int dist){
    if (x==t)return dist;
    for (int& i=cur[x];i!=-1;i=next[i]){
        int v=to[i];
        if (dep[v]==dep[x]+1&&w[i]!=0){
            int d=dfs(v,min(dist,w[i]));
            if (d){
                w[i]-=d;
                w[i^1]+=d;
                return d;
            }
        }
    }
    return 0;
}
int dinic(){
    int ans=0;
    while (bfs()){
        for (int i=0;i<=t;i++)cur[i]=head[i];
        while (int di=dfs(s,inf))ans+=di;
    }
    return ans;
}
void dp(){
    for (int i=n;i>=1;i--){
        f[i]=1;
        for (int j=n;j>i;j--){
            if (val[j]>=val[i]){
                f[i]=max(f[i],f[j]+1);
            }
        }
        ass=max(ass,f[i]);
    }
}
int main(){
    memset(head,-1,sizeof(head));
    memset(next,-1,sizeof(next));
    n=Read();//m=Read();s=Read();t=Read();
    s=0;t=(n<<1)+1;
    /*for (int i=1;i<=m;i++){
        b=Read();k=Read();l=Read();
        if (b==k)continue;
        add(b,k,l);add(b,j,0);
    }
    printf("%d",dinic());*/
    for (int i=1;i<=n;i++)val[i]=Read();
    dp();printf("%d\n",ass);
    for (int i=1;i<=n;i++){
        if (f[i]==ass)add(s,i,1);add(i,i+n,1);
        for (int j=i+1;j<=n;j++){
            if (val[j]>=val[i]&&f[i]==f[j]+1){
                add(i+n,j,1);
            }
        }
        if (f[i]==1)add(i+n,t,1);
    }
    printf("%d\n",dinic());
    add(n,n+n,inf);add(n+n,t,inf);
    if (f[1]==ass)add(s,1,inf),add(1,1+n,inf);
    printf("%d",dinic()+ass);
    return 0;
}

|