linwanbo @ 2024-10-25 17:31:30
#include<bits/stdc++.h>
using namespace std;
int head[250001],num_edge=-1,s,t,n;
int a[501];
struct Edge
{
int next,to,dis;
}edge[250001];
void push(int from,int to,int dis)
{
edge[++num_edge].next=head[from];
edge[num_edge].to=to;
edge[num_edge].dis=dis;
head[from]=num_edge;
}
void add(int u,int v,int val){
push(u,v,val);
push(v,u,0);
}
int d[250001],f[250001],cur[250001];
inline bool bfs()
{
memset(d,0,sizeof(d));
d[s]=1;
queue<int> q;
q.push(s);
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=head[x];i!=-1;i=edge[i].next)
{
int y=edge[i].to;
if(!d[y]&&edge[i].dis)
{
d[y]=d[x]+1;
q.push(y);
}
}
}
if(!d[t]) return 0;
else return 1;
}
int dfs(int pos,int dis)
{
if(pos==t) return dis;
for(int i=cur[pos];i!=-1;i=edge[i].next)
if(d[edge[i].to]==d[pos]+1&&edge[i].dis>0)
{
int data=dfs(edge[i].to,min(dis,edge[i].dis));
if(data>0)
{
edge[i].dis-=data;
edge[i^1].dis+=data;
if(edge[i].dis) cur[pos]=i;
return data;
}
}
return 0;
}
inline int Dinic()
{
int ans=0;
while(bfs())
{
memcpy(cur,head,sizeof(cur));
while(int data=dfs(s,0x3f3f3f3f))
ans+=data;
}
return ans;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
f[i]=1;
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);
int ans1=0;
for(int i=1;i<=n;i++)
ans1=max(ans1,f[i]);
cout<<ans1<<endl;
s=0;
t=n+n+1;
memset(head,-1,sizeof(head));
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);
for(int i=1;i<=n;i++)
if(f[i]==ans1) 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[j]==f[i]-1)
add(j+n,i,1);
int ans2=Dinic();
cout<<ans2<<endl;
add(1,1+n,0x3f3f3f3f);
add(s,1,0x3f3f3f3f);
if(f[n]==ans1) add(n,n+n,0x3f3f3f3f),add(n+n,t,0x3f3f3f3f);
ans2+=Dinic();
cout<<ans2;
}
我这个代码为啥只有92啊,12点过不去