[文章目录]
Description
给定正整数序列 x1,., xn 。(n<=500)
（1）计算其最长不降子序列的长度 s。
（2）计算从给定的序列中最多可取出多少个长度为 s的不降子序列。
（3）如果允许在取出的序列中多次使用 x1和 xn，则从给定序列中最多可取出多少个长度为 s的不降子序列。
设计有效算法完成（ 1）（2）（3）提出的计算任务。
第一问就不说了。第二问其实是取出一个最长子序列后再从剩下的子序列中取出一个，反复操作，问最多能取几个。就是每个元素只能用一次，问我们能造多少个最长上升子序列。网络流，每个点差点，限流，流量为1，向dp值为当前元素dp值+1且比当前元素大的点连边，流量为1，然后源点向所有dp值为1的点连边，dp值为s的向汇点连边。最大流就是答案。
第三问就是1，n可以用多次，相当于将限流流量改为inf。并且注意，s到1的流量和n到t的流量也改为inf
（垃圾数据，觉得应该有只有一个元素的特判的233）.
#include <vector>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;
int n,b[550],ans1,ans2,s,t;
int dp[550],c[550],cnt,mx,tmp;
vector<int>v[550];
int head[1100],to[5000],nxt[5000],f[5000],tot=1;
void add(int x,int y,int z)
{
to[++tot]=y;
f[tot]=z;
nxt[tot]=head[x];
head[x]=tot;
to[++tot]=x;
f[tot]=0;
nxt[tot]=head[y];
head[y]=tot;
}
int dis[1100];
queue<int>q;
bool bfs()
{
while(!q.empty()) q.pop();
memset(dis,-1,sizeof(dis));
dis[s]=0;int x;q.push(s);
while(!q.empty())
{
x=q.front();q.pop();
for(int i=head[x];i;i=nxt[i])
if(f[i]>0&&dis[to[i]]<0)
{
dis[to[i]]=dis[x]+1;
if(to[i]==t) return true;
q.push(to[i]);
}
}
return false;
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int xx,tmp=flow;
for(int y,i=head[x];i;i=nxt[i])
if(f[i]>0&&dis[y=to[i]]==dis[x]+1)
{
xx=dinic(y,min(f[i],tmp));
if(!xx) dis[y]=-1;
f[i]-=xx;f[i^1]+=xx;tmp-=xx;
if(!tmp) break;
}
return flow-tmp;
}
int main()
{
c[0]=-1<<30;
scanf("%d",&n);
s=n+n+1,t=s+1;
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
for(int i=1;i<=n;i++)
{
if(b[i]>=c[cnt]) c[++cnt]=b[i],dp[i]=cnt;
else
{
int l=1,r=cnt+1,mid;
while(l<r)
{
mid=l+r>>1;
if(c[mid]<=b[i]) l=mid+1;
else r=mid;
}
c[l]=b[i]; dp[i]=l;
}
}
for(int i=1;i<=n;i++)
{
add(i,i+n,1);
int id=dp[i]-1;
for(int j=v[id].size()-1;j>=0;j--)
if(b[i]>=b[v[id][j]]) add(v[id][j]+n,i,1);
else break;
v[dp[i]].push_back(i);
}
for(int i=v[1].size()-1;i>=0;i--) add(s,v[1][i],1);
for(int i=v[cnt].size()-1;i>=0;i--) add(v[cnt][i]+n,t,1);
while(bfs()) ans1+=dinic(s,1<<30);
for(int i=2;i<=tot;i+=2) f[i]+=f[i^1],f[i^1]=0;
for(int i=head[1];i;i=nxt[i])
if(to[i]==n+1) f[i]=inf;
for(int i=head[n];i;i=nxt[i])
if(to[i]==n+n) f[i]=inf;
for(int i=head[s];i;i=nxt[i])
if(to[i]==1) f[i]=inf;
for(int i=head[t];i;i=nxt[i])
if(to[i]==n+n) f[i^1]=inf;
while(bfs()) ans2+=dinic(s,1<<30);
printf("%d\n%d\n%d",cnt,ans1,ans2);
return 0;
}