92分求助

P2766 最长不下降子序列问题

Kniqht @ 2023-12-16 18:09:48

就WA了一个点,有没有大佬也有同样错误啊?

这两天有难度的题都调不出来,真破防了

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,M=1e6+10,inf=0x3f3f3f3f;
int n,m,s,t;
int h[M],e[M*2],ne[M*2],w[M*2],idx,l[210][210];
void add(int a,int b,int c){
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
    e[idx]=a,ne[idx]=h[b],w[idx]=0,h[b]=idx++;
}
int a[N];
int cur[N],d[N];
bool bfs(){
    for(int i=1;i<=2*n+1;i++) d[i]=inf;
    queue<int> q;
    q.push(s);
    d[s]=0;
    cur[s]=h[s];
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=h[x];~i;i=ne[i]){
            int j=e[i];
            if(w[i]>0&&d[j]==inf){
                q.push(j);
                cur[j]=h[j];
                d[j]=d[x]+1;
                if(j==t) return 1;
            }
        }
    }
    return 0;
}
int dinic(int x,int flow){
    if(x==t) return flow;
    int res=0,k;
    for(int i=cur[x];~i&&flow;i=ne[i]){
        cur[x]=i;
        int j=e[i]; 
        if(w[i]>0&&d[j]==d[x]+1){
            k=dinic(j,min(flow,w[i]));
            if(!k) d[j]=inf;
            w[i]-=k;
            w[i^1]+=k;
            res+=k; 
            flow-=k;
        }
    }
    return res;
} 
int maxflow(){
    int flow=0;
    while(bfs()) flow+=dinic(s,inf);
    return flow; 
}
int f[N];
signed main(){
    memset(h,-1,sizeof(h));
    scanf("%lld",&n);
    s=0,t=2*n+1;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]),f[i]=1;
    int len=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++)
            if(a[j]<=a[i]) f[i]=max(f[i],f[j]+1);
        len=max(len,f[i]);
    }
    printf("%lld\n",len);
    for(int i=1;i<=n;i++) add(i,i+n,1);
    for(int i=1;i<=n;i++){
        if(f[i]==1) add(s,i,1);
        if(f[i]==len) add(i+n,t,1);
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
            if(a[j]<=a[i]&&f[i]==f[j]+1) add(j+n,i,1);
    int ans;
    printf("%lld\n",ans=maxflow());
    add(1,1+n,inf);add(s,1,inf);
    if(f[n]==len) add(n+n,t,inf),add(n,n+n,inf);
    printf("%lld",ans+maxflow());
    return 0;
}

by Kniqht @ 2023-12-16 18:45:15

原来是特判n=1


|