刚学OI一秒钟,wa了一个点

P2766 最长不下降子序列问题

红色OI再临 @ 2019-07-20 16:43:19

WA了第三个点

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
#define re register int 
#define MN 1001
#define inf 1<<30
using namespace std;
int f[MN];
int a[MN];
struct tu{
    int v,w,nxt;
}e[MN*2];
int cnt=1,head[MN];
int n,m,s,t,maxflow;
void add(int u,int v,int w){
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
struct front{
    int u,edge;
}pre[2*MN];
int vis[MN],dep[MN];
bool bfs(){
    memset(dep,0x3f3f3f3f,sizeof(dep));
    memset(vis,0,sizeof(vis));
    dep[s]=0;
    queue<int>q;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(re i=head[u];i;i=e[i].nxt){
            int v=e[i].v;
            if(dep[v]>dep[u]+1&&e[i].w){
                dep[v]=dep[u]+1;
                if(vis[v]==0){
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return dep[t]!=0x3f3f3f3f;
}
int dfs(int u,int flow){//flow为当前路上最短边权
    int rlow=0;
    if(u==t)return flow;
    for(re i=head[u];i;i=e[i].nxt){
        int v=e[i].v;
        if(e[i].w&&dep[v]==dep[u]+1){
            if(rlow=dfs(v,min(flow,e[i].w))){
                e[i].w-=rlow;
                e[i^1].w+=rlow;
                return rlow;
            }
        }
    }
    return 0;
}
int dinic(){
    int lowflow;
    while(bfs()){
        while(lowflow=dfs(s,inf))maxflow+=lowflow;
    }
    return maxflow;
}
int main(){
    scanf("%d",&n);
    for(re i=1;i<=n;i++)
    scanf("%d",&a[i]),f[i]=1;
    s=0;t=2*n+1;
    for(re i=2;i<=n;i++)
    for(re j=1;j<i;j++)
    {
        if(a[j]<=a[i])f[i]=max(f[i],f[j]+1);
    }
    int ans1=0;
    for(re i=1;i<=n;i++)
        ans1=max(ans1,f[i]);
        printf("%d\n",ans1);
        if(ans1==1){
            printf("%d\n",n);
            printf("%d\n",n);
            return 0;
        }
    for(re i=1;i<=n;i++)
        add(i,i+n,1),add(i+n,i,0);
    for(re i=1;i<=n;i++)
    {
        if(f[i]==1)add(s,i,1),add(i,s,0);
        if(f[i]==ans1)add(i+n,t,1),add(t,i+n,0);
    }
    for(re i=1;i<=n;i++)
        for(re j=1;j<i;j++)
        if(a[j]<=a[i]&&f[i]==f[j]+1)add(j+n,i,1),add(i,j+n,0);
        printf("%d\n",dinic());
    add(1,n+1,inf);add(n+1,1,0);
    add(s,1,inf);add(1,s,0);
    if(f[n]==ans1)add(n,n*2,inf),add(n*2,n,0),add(n*2,t,inf),add(t,n*2,0);
    printf("%d\n",dinic());
return 0;
}

by 红色OI再临 @ 2019-07-20 16:58:30

@foxdemon 确实认识QAQ


by foxdemon @ 2019-07-20 16:59:06

@红色OI再临 居然猜对了qwq


by 红色OI再临 @ 2019-07-20 17:01:05

@foxdemon 他建议我面向数据编程(雾)


by Lovable_Wind @ 2019-07-20 17:03:25

走自己的路


by Lovable_Wind @ 2019-07-20 17:03:37

别听别人的批判


by 红色OI再临 @ 2019-07-20 17:05:24

@klssxbc0002 嗯嗯

批判还是要听的


by 红色OI再临 @ 2019-07-20 17:05:56

错误已找到:数组开小

此帖终结


by Lovable_Wind @ 2019-07-20 17:10:27

@红色OI再临 别听太多在你正常学习并没做错时的批判


by tanao @ 2019-07-29 20:54:55

fAKe!肥克!


上一页 |