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